/*
题目：
	给定一个m*n的棋盘，每格放一个礼物(每个礼物的值大于0)，
	从左上角出发，向下或向右走到达右下角，得到的礼物和最大。
*/
/*
思路：
	f(i,j)=max[f(i-1,j),f(i,j-1)] + a[i,j]
*/
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>


using namespace std;


int getMaxValue(const int* values,int rows,int cols){
    if(rows <= 0 || cols <= 0) return 0;
    int *maxValues = new int[cols];
    maxValues[0] = values[0];

    for(int col = 1; col < cols; col++){
        maxValues[col] = maxValues[col-1] + values[col];
    }

    for(int row = 1; row < rows; row++){
        for(int col = 0; col < cols; col++){
            if(col == 0){
                maxValues[0] = maxValues[0] + values[row * cols + col];
            }else{
                maxValues[col] = max(maxValues[col-1],maxValues[col]) + values[row * cols + col];
            }
        }
    }
    return maxValues[cols - 1];
}


int main(){
    int values[]={1,10,3,8,12,2,9,6,5,7,4,11,3,7,16,5};
    cout<<getMaxValue(values,4,4);
    return 0;
}