第二十六天

最大子数组和

53. 最大子数组和 - 力扣（LeetCode）

动态规划问题

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];
        int res = dp[0];
        for(int i = 1; i < len; i++){
            dp[i] = Math.max(dp[i - 1] + nums[i],nums[i]);
            res = Math.max(dp[i],res);
        }
        return res;
    }
}

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,INT_MIN);
        dp[0] = nums[0];
        int ans = dp[0];
        for(int i = 1;i < n;i++){
            dp[i] = max(dp[i - 1]+ nums[i],nums[i]);
            ans = max(dp[i],ans);
        }
        return ans;
    }
};