算法学习 day26

第二十六天

最大子数组和

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int maxSubArray(vector& nums) {
        int n = nums.size();
        vector 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14