经典的动态规划题
其思路是把所有的和都算出来, 当然不能简单粗暴的直接相加, 要利用上一次计算出的结果加速第二次的运算
- class Solution {
- public:
- int FindGreatestSumOfSubArray(vector array) {
- int size = array.size();
- int max = INT_MIN;
- //dp 数组初始化, dp[i][j] 表示从 i 到 j 的和, 例如 dp[0][1] 表示 array[0]+array[1]
- vector dp(size,vector(size));
- dp[0][0] = array[0];
- for(int i=0;i<size;i++)
- {
- for(int j=1;j<size;j++)
- {
- if(i>j) continue;// 确保 i 在 j 的前面
- dp[i][j] = dp[i][j-1] + array[j];
- if(dp[i][j]> max)
- {
- max = dp[i][j];
- }
- }
- }
- return max;
- };
来源: http://www.bubuko.com/infodetail-3387010.html