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

• 一、53. 最大子数组和
• • leetcode 53 java
  • 思路
  • • 动态规划 dp[i]+=dp[i-1] (dp[i-1]>0)
• 总结

53. 最大子数组和

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

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        for(int i = 0; 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
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}