最大连续元素和
已知数组x[ ]储存了一组整数,请写一个程序,找出在数组中连续元素的和中最大的一个。举例而言,如果有数组1,2,-6,3,-2,4,-1,3,2,-4,那么连续的元素和有1 + 2 = 3,1 + 2 + (-6) = -3,2 + (-6) = -4,。。。,但最大的就是3 + (-2) + 4 + (-1) + 3 + 2这一段,值为9。这个题目通常叫做最大连续元素和问题,或者叫做最大连续子数组。
一个自然的办法是使用双重循环,但是性能不好。这个问题要求O(n)解法,需要动点脑筋。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public class MaximumSubarray {
public static int maxSubArray(int[] nums) {
int result = nums[0];
int sum = nums[0];
for (int i = 1; i < nums.length; i++) {
if (sum < 0) {
sum = 0;
}
sum += nums[i];
result = Math.max(result, sum);
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 2, -6, 3, -2, 4, -1, 3, 2, -4};
System.out.println(maxSubArray(nums));
}
}
还有一种是分治的方法,效率慢一些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
32
33
34
35
36public class MaximumSubarray {
public static int maxSubArray(int[] nums) {
return maxSubArray(nums, 0, nums.length - 1);
}
public static int maxSubArray(int[] nums, int left, int right) {
if (left > right) {
return Integer.MIN_VALUE;
} else if (left == right) {
return nums[left];
} else {
int middle = (right - left) / 2 + left;
int leftMax = maxSubArray(nums, left, middle);
int rightMax = maxSubArray(nums, middle + 1, right);
int sum = 0;
int maxToLeft = Integer.MIN_VALUE;
for (int i = middle; i >= left; i--) {
sum += nums[i];
maxToLeft = Math.max(maxToLeft, sum);
}
sum = 0;
int maxToRight = Integer.MIN_VALUE;
for (int i = middle + 1; i <= right; i++) {
sum += nums[i];
maxToRight = Math.max(maxToRight, sum);
}
int result = maxToLeft + maxToRight;
result = Math.max(result, leftMax);
result = Math.max(result, rightMax);
return result;
}
}
public static void main(String[] args) {
int[] nums = {1, 2, -6, 3, -2, 4, -1, 3, 2, -4};
System.out.println(maxSubArray(nums));
}
}