最大子段和（一）

问题描述：

给定n个整数(可能为负数)组成的序列a1,a2,a3,...,an, 求该序列子段和的最大值

例如：

X={-2, 11, -4, 13, -5, -2}, 其最大子段和为20

最大子段为：11，-4，13

解法一：穷举法

列举所有的可能，求其中的最大值

算法实现如下：

/*
 * description: 最大子段和问题
 * 问题描述：给定n个整数(可能为负数)组成的序列a1,a2,a3,...,an,
 * 求该序列子段和的最大值
 * 解法一：穷举法，选取其中一个最大的值
 * 
 * auther: cm
 * date: 2010/11/19
 */
public class MaxSubSum
{
	//穷举法
	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 sum = 0;
				for (int k = i; k <= j; k++)
				{
					sum += a[k];
				}
				if (sum > maxSum)
				{
					maxSum = sum;
				}
			}
		}
		return maxSum;
	}

	//穷举法改进,减少一层循环
	public static int maxSubSum2(int[] a)
	{
		int maxSum = 0;
		
		for (int i = 0; i < a.length; i++)
		{
			int sum = 0;

			for (int j = i; j < a.length; j++)
			{
				sum += a[j];
				
				if (maxSum < sum)
				{
					maxSum = sum;
				}
			}
		}

		return maxSum;
	}
	public static void main(String[] args) 
	{
		int[] a = {-2, 11, -4, 13, -5, -2};
		//System.out.println(MaxSubSum.maxSubSum1(a));
		System.out.println(MaxSubSum.maxSubSum2(a));
	}
}