题目描述：JZ42 连续子数组的最大和

思路：动态规划

• 状态表示：dp[i]
  • 集合：表示以下标 i 结尾的连续数组的和
  • 属性：最大
• 状态计算：以 array 开始划分
  • 加当前下标 i：dp[i] = dp[i-1]+array[i]
  • 当前下标 i 重新开始：array[i]

朴素版写法

• 时间复杂度：O(n)，空间复杂度：O(n)

class Solution {
public:
  	static const int N = 2e5 +10;
  	int dp[N];
  	int FindGreatestSumOfSubArray(vector<int> array) {
      	if(array.size() == 1) return array[0];
      	// 初始化
      	memset(dp, 0, sizeof dp);
      	dp[0] = array[0];
      	// 保存结果,因为不知道，以那个下标结尾才是最大的那个连续子序列
      	// 所以需要记录，每次更新 dp 数组时，得到的最大值
      	int res = dp[0];
      	// dp 
      	for (int i = 1; i < array.size(); ++i) {
          	dp[i] = max(dp[i-1]+array[i], array[i]);
          	res = max(res, dp[i]);
        }
      
      	return res;
    }
}

优化版：滚动数组

• 时间复杂度：O(n)，空间复杂度：O(1)
• 每次 dp 的更新，都只用到了，上一个的状态，比如 dp[i],只需要知道i-1的状态， 所以可以将空间复杂度优化到常数级别。

class Solution {
public:
  	int FindGreatestSumOfSubArray(vector<int> array) {
      	int pre = 0, res = array[0];
      	for (auto& x : array) {
          	pre = max(pre + x, x);
          	res = max(res, pre);
        }
      	return res;
    }
}

😿😿😿😿😿😿😿