//
// Created by bleedingfight on 2020年7月4日.
//

#include "maxValue.h"
int maxValue(std::vector<std::vector<int>>& grid){
 const int rows = grid.size();
 if(rows == 0)
 return 0;
 const int cols = grid[0].size();
 if(cols == 0)
 return 0;
 std::vector<int>sum_dp = std::vector<int>(cols,0);
 for(int row =0;row<rows;row++){
 for(int col=0;col<cols;col++){
 if(col == 0 && row == 0)
 sum_dp[col] = grid[row][col];
 else if(row == 0 && col!=0)
 sum_dp[col] = grid[row][col]+sum_dp[col-1];
 else if(row !=0 && col==0)
 sum_dp[col] = grid[row][col]+sum_dp[col];
 else
 {
 int left = sum_dp[col-1];
 int upper = sum_dp[col];
 if(left>upper){
 sum_dp[col]=left+grid[row][col];
 } else{
 sum_dp[col]=upper+grid[row][col];
 }
 }
 }
 }
 return sum_dp[cols-1];
}