求最大子序列和的问题

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

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

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;
	}

阅读剩下更多