LeetCode-53. 最大子数组和-暴力+类DP+前缀和

Problem: 53. 最大子数组和
每日一题。

Code

暴力-滑动窗口（超时）

class Solution {  
    public int maxSubArray(int[] nums) {  
        int len = nums.length;  
        int max = Integer.MIN_VALUE;  
        int l, r;  
        for (l = 0; l < len; l++) {  
            int sum = nums[l];  
            max = Math.max(max, sum);  
            for (r = l + 1; r < len; r++) {  
                sum += nums[r];  
                max = Math.max(max, sum);  
            }  
        }  
        return max;  
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

暴力优化->动态规划(贪心)

从纯暴力->类贪心，dp的详解-暗里
统计所有以nums[i]结尾的子数组为目标。

class Solution {  
	public int maxSubArray(int[] nums) {  
	    int len = nums.length;  
	    int max = Integer.MIN_VALUE;  
	    int sum = 0;// 当前和  
	    for (int i = 0; i < len; i++) {  
	        if (i == 0) {  
	            sum = nums[i];  
	        } else {  
	            // 动态规划-贪心  
	            sum = Math.max(sum + nums[i], nums[i]); // 子数组和为前一个元素和当前元素的和中的较大值  
	        }  
	        max = Math.max(max, sum);  
	    }  
	    return max;  
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

前缀和

前缀和做法：本质是买卖股票问题-灵茶山艾府

class Solution {  
    public int maxSubArray(int[] nums) {  
        int max = Integer.MIN_VALUE;  
        int minPreSum = 0;  
        int preSum = 0;  
        for (int x : nums) {  
            preSum += x; // 当前的前缀和  
            max = Math.max(max, preSum - minPreSum); // 减去前缀和的最小值  
            minPreSum = Math.min(minPreSum, preSum); // 维护前缀和的最小值  
        }  
        return max;  
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13