给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

贪心算法

核心思想就是检查之前 i-1 的元素和，如果小于零就舍弃——对应下面第六行代码

1 class Solution {
2 public:
3 int maxSubArray(vector& nums) {
4 int cur_nums = 0 , max_nums = INT_MIN;
5 for(int i = 0;i < nums.size();i++){
6 cur_nums = max(nums[i],cur_nums + nums[i]);
7 max_nums = max(cur_nums,max_nums);
8 }
9 return max_nums;
10 }
11 };

动态规划

关于动态转移方程建立的分析如下：

摘自 https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/

1 class Solution {
2 public:
3 int maxSubArray(vector& nums) {
4
5 int max_sum = nums[0];
6 vector dp (nums.size());
7 dp[0] = nums[0];
8 for(int i = 1 ;i < dp.size(); i++){
9 dp[i] = max(dp[i-1] + nums[i], nums[i]);
10 max_sum = max(max_sum,dp[i]);
11 }
12 return max_sum;
13 }
14 };

上面时间复杂度为O(n)，空间复杂度为O(n)   但是这题从动态转移方程可以看出dp[i] 只依赖于前面 dp[i-1]  。

所以可以不使用数组来保存dp，用int变量来保存。 这样得到优化后的空间复杂度为O(1)的代码如下

1 class Solution {
2 public:
3 int maxSubArray(vector& nums) {
4
5 int max_sum = nums[0];
6 int dp = nums[0];
7 for(int i = 1 ;i < nums.size(); i++){
8 dp = max(dp + nums[i], nums[i]);
9 max_sum = max(max_sum,dp);
10 }
11 return max_sum;
12 }
13 };