题解 | #连续子数组的最大和#

渐渐对动态规划有感觉了

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
      //  dp[i] 表示结尾元素为i下标的子数组的和的最大值
      //  最后一个不一定就是和最大值，因为子数组不一定取到最后一个元素
      //  每次取子数组时，记录下最大值
      int res = -200;
      std::vector<int> dp(array.size(), 0);
      
      //  假设每个元素都为子数组时和最大
      for (int i = 0; i < array.size(); ++i) {
        dp[i] = array[i];
      }
      
      for (int i = 0; i < array.size(); ++i) {
        dp[i] = std::max(dp[i], dp[i - 1] + array[i]);
        //  以某下标i结尾的子数组，其和达到最大，记录下来
        res = std::max(res, dp[i]);
      }
      
      return res;
    }
};