Find the Minimum Weight Path in Triangle

EPI 17.8

Geeks change minimum to maximum

Description:

We have given numbers in form of triangle, by starting at the top of the triangle and moving to adjacent numbers on the row below, find the maximum total from top to bottom.

Example:

Input : 
   3
  7 4
 2 4 6
8 5 9 3
Output : 23
Explanation : 3 + 7 + 4 + 9 = 23 

Input :
   8
 -4 4
 2 2 6
1 1 1 1
Output : 19
Explanation : 8 + 4 + 6 + 1 = 19

Idea:

自底向上。

用一个array作为存储就可以。

Code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maximumPath(const vector<vector<int>>& arr){
    int lastSize=arr.back().size();
    vector<int> tmpArr(arr.back().begin(), arr.back().end());

    for(int i= arr.size()-2; i>=0; i--){
        for(int j=0; j<=i; j++){
            tmpArr[j]= arr[i][j] + max(tmpArr[j], tmpArr[j+1]);
        }
    }
    return tmpArr[0];
}

int main(){
    vector<vector<int>> arr;
    arr.push_back({3});
    arr.push_back({7,4});
    arr.push_back({2,4,6});
    arr.push_back({8,5,9,3});
    cout<<maximumPath(arr);
}