[brother hero July training] day 28: dynamic planning

---

One 、53. Maximum subarray and

53. Maximum subarray and

Give you an array of integers nums , Please find a continuous subarray with the largest sum （ A subarray contains at least one element ）, Return to its maximum and .
Subarray Is a continuous part of the array .

leetcode 53 java

Ideas

Dynamic programming 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;
    }
}

---

summary