53.最大子数组和

双重循环遍历数组的所有子序列，随时记录count，一旦发现count>max，赋值max=count。

//蛮力法
class Solution {
public:
    int maxSubArray(vector& nums) {
        int numsSize = nums.size();
        int max = INT_MIN;
        for (int i=0; i
            int count = 0;
            for (int j=i; j
                count += nums[j];
                if (count > max)    max = count;
            }
        }
        
        return max;
    }
};

用 dp[i] 存储以 nums[i] 为结尾的最大子数组和；若此子序列比 nums[i] 还小，保留该元素即可。

dp每产生一个新元素，res 更新记录；

//动态规划法
class Solution {
public:
    int maxSubArray(vector& nums) {
        int numsSize = nums.size();
        int res = INT_MIN;
        //定义数组及初始化
        vector dp(numsSize);
        dp[0] = nums[0];
        res = dp[0];
        //给数组赋值
        for (int i=1; i
            dp[i] = max(dp[i-1]+nums[i], nums[i]);
            res = max(dp[i], res);
        }
        return res;
    }
};

因为每次只考虑 dp 的 i-1 项，所以用 int 保存即可，大大减小复杂度。

//优化动态规划
class Solution {
public:
    int maxSubArray(vector& nums) {
        int numsSize = nums.size();
        int res = INT_MIN;
        int dp = nums[0];
        res = dp;
        for (int i=1; i
            dp = max(dp+nums[i], nums[i]);
            res = max(dp, res);
        }
        return res;
    }
};

动态规划法的思路是用 max() 判断是否加 dp(i-1) ;

贪心法的思路是用 max() 判断是否加 nums[i] ;

//贪心法
class Solution {
public:
    int maxSubArray(vector& nums) {
        int numsSize = nums.size();
        int res = INT_MIN;
        int sum = 0;
        for (int i=0; i
            sum += nums[i];
            res = max(res,sum);
            if (sum < 0) {
                sum = 0;
            }
        }
        return res;
    }
};

1. 初始值必须是理论最小值，因为有全负数的子序列；
2. 遇到“最大”和“连续”问题，首选动态规划法；