求最大子序列和的问题

问题：给定（可能有负数）整数A1，A2，…，An，求∑Ak的最大值。（所有整数均为负数，则最大子序列和为0）。

1.穷举法
这种算法就是穷举所有的可能。for循环中的循环变量反映了Java中数组从0开始而不是从1开始这样一个事实。还有，本算法并不计算实际的子序列；实际的计算还要添加一些额外的代码。这个算法的运行时间为O(N3)

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int maxSubSum1(int[] a) {
		int maxSum = 0;
		for(int i = 0; i < a.length; i++)
			for(int j = i; j < a.length; j++){
			int thisSum = 0;
			for(int k = i; k <= j; k++)
				thisSum += a[k];

			if(thisSum > maxSum)
				maxSum = thisSum;
		}
		return maxSum;
	}

2.在算法1的基础上进行改进，通过观察∑(j,k=i)Ak = Aj + ∑(j-1,k=i)Ak而看出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int maxSubSum2(int[] a) {
		int maxSum = 0;
		for(int i = 0; i < a.length; i++){
			int thisSum = 0;
			for(int j = i; j < a.length; j++){
				thisSum += a[j];

				if(thisSum > maxSum)
					maxSum = thisSum;
			}
		}
			
		return maxSum;
	}

3.对于这个问题有一个递归和相对复杂的O(NlogN)解法，这个算法采用了一种“分治”策略。其想法是把问题分成两个大致相等的子问题，然后递归地对他们求解，这是“分”的部分。“治”阶段将两个子问题的解修补到一起并可能再做些少量的附加工作，最后得到整个问题的解。

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
public static int maxSubSum3(int[] a, int left, int right) {
	if(left == right)//基本情形
		if(a[left] > 0)
			return a[left];
		else
			return 0;

	int center = (left + right) / 2;
	int maxLeftSum = maxSumRec(a, left, center);
	int maxRightSum = maxSumRec(a, center + 1, right);
	int maxLeftBorderSum = 0;
	int leftBorderSum = 0;
	for(int i = center; i >= left; i--){
		leftBorderSum += a[i];
		if(leftBorderSum > maxLeftBorderSum)
			maxLeftBorderSum = leftBorderSum;
	}		
	int maxRightBorderSum = 0;
	int rightBorderSum = 0;
	for(int i = center + 1; i <= right; i++){
		rightBorderSum += a[i];
		if(rightBorderSum > maxRightBorderSum)
			maxRightBorderSum = rightBorderSum;
	}

	return (maxLeftSum + maxRightSum)>(maxLeftSum > maxRightSum ? maxLeftSum : maxRight)?
	(maxLeftSum + maxRightSum):(maxLeftSum > maxRightSum ? maxLeftSum : maxRight)
}

4.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int maxSubSum4(int[] a) {
		int maxSum = 0;
		int thisSum = 0;
			
		for(int j = 0; j < a.length; j++){
			thisSum += a[j];

			if(thisSum > maxSum)
				maxSum = thisSum;
			else if(thisSum < 0)
				thisSum = 0;
		}
		
			
		return maxSum;
	}