【LeetCode热题100】--53.最大子数组和

53.最大子数组和

使用动态规划：

• 状态定义：设动态规划列表dp，dp[i]代表以元素nums[i]为结尾的连续子数组最大和

• 转移方程：若dp[i-1]≤0,说明dp[i-1]对dp[i]产生负贡献，即dp[i-1]+nums[i]还不如nums[i]本身大

• 初始状态：dp[0]=nums[0]，即以nums[0]结尾的连续子数组最大和为nums[0]
• 返回值：返回dp列表中的最大值，代表全局最大值

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        //dp[i]表示：以nums[i]结尾的连续子数组的最大和
        int[] dp = new int[len];
        dp[0] = nums[0];
        for(int i=1;i<len;i++){
            if(dp[i-1] > 0){
                dp[i] = dp[i-1]+nums[i];
            }else{
                dp[i] = nums[i];
            }
        }
        //遍历求出结果
        int res = dp[0];
        for(int i =0;i<len;i++){
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21