leetcode解题: Maximum Subarray (53)

发表于 | 分类于

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
Practice

解法1：DP with O(N) 空间

用经典的DP思想可以解决，dp数组存的是以i结尾的前i个数字的max subarray，那么可以得到这样的递推关系
dp[i] = Max(dp[i - 1] + A[i], A[i])
意思就是说以i结尾的最大的子数组和要么是自己，要么是前一个子数组和加上自己。可以写出如下的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxSubArray(int[] nums) {
	
	int[] dp = new int[nums.length];
	dp[0] = nums[0];
	int max = dp[0];
	
	for (int i = 1; i < nums.length; i++) {
		dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
		max = Math.max(dp[i], max);
	}
	
	return max;
}

解法1优化: DP with O(1) 空间

观察上面的解法可以发现，实际上我们不需要维护一个数组来记录每一个点的最大和。
我们可以只维护一个变量sum,来记录从0到i的和。如果sum一旦小于0，那么对下一个dp数值的计算一定用不上sum,所以此时可以设置为0. 代码如下

1
2
3
4
5
6
7
8
9
10
11
12
public int maxSubArray(int[] nums) {
	
	int sum = 0;
	int max = Integer.MIN_VALUE;
	for (int i = 0; i < nums.length; i++) {
		sum += nums[i];
		max = Math.max(sum, max);
		if (sum < 0) {
			sum = 0;
		}
	return max;
}

解法2: 前缀和数组的思路，O(N) time + O(1) space

基本思想是：如果把数组中每一个元素都加起来，我们可以得到一个累积的和，那么这个问题实际上就变成了
best time to buy and sell stock I的问题，从左至右寻找最小的mininum sum,然后将当前的sum和minSum相减再和全局的最大值比较得出结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int maxSubArray(int[] nums) {
	
	int sum = 0;
	
	int min = 0;
	
	int profit = nums[0];
	
	for (int i = 0; i < nums.length; i++) {
		profit = Math.max(sum + nums[i] - min, profit);
		sum += nums[i];
		min = Math.min(sum, min);
	}
	return profit;
}

解法3：用Divide & Conquer思想：O(NlogN)

具体的思路是把原来的array一分为二，那么最大的子数组和一定是在1.左面的数组，2.右面的数组，3.跨越左面和右面的数组
左面和右面用递归的方式计算。跨越中点的数组一定包含mid point,往右面扫描找出最大的，往左面扫描找出最大的，最后比较三个数得出结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int maxSubArray(int[] nums) {
	return helper(nums, 0, nums.length - 1);
}
public int helper(int[] A, int left, int right) {
	if (left >= right) {
		return A[left];
	}
	
	// Divide into left and right array
	int mid = left + (right - left) / 2;
	int lmax = helper(A, left, mid - 1);
	int rmax = helper(A, mid + 1, right);
	
	// Merge and Conquer
	int mmax = A[mid];
	int temp = mmax;
	// Scan to left
	for (int i = mid - 1; i >= left; i--) {
		temp += A[i];
		mmax = Math.max(mmax, temp);
	}
	
	// Scan to right
	temp = mmax;
	for (int i = mid + 1; i <= right; i++) {
		temp += A[i];
		mmax = Math.max(mmax, temp);
	}
	return Math.max(mmax, Math.max(lmax, rmax));
}