【英雄哥七月集训】第 28天：动态规划

---

一、53. 最大子数组和

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。

leetcode 53 java

思路

动态规划 dp[i]+=dp[i-1] (dp[i-1]>0)

class Solution {
    
    public int maxSubArray(int[] nums) {
    
        int n = nums.length;
        int[] dp = new int[n];
        for(int i = 0; i<n ;i++){
    
            dp[i] = nums[i];
            if(i>0 && dp[i-1]>0){
    
                dp[i]+=dp[i-1];
            }
        }

        int max = -10010;
        for(int i = 0; i<n ;i++){
    
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

---

总结