面试题5：求子数组的最大和

面试题五：求子数组的最大和

5.求子数组的最大和
题目：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为 O(n)。
a[] = {-2,3,-1,4,-7,-3,4,5,-2}
像这个数组的最大子数组是｛4,5｝
思路一:这种情况时间复杂度大于0(n);
 -2,3,-1,4,-7,-3,4,5,-2
a.开辟两个下标值,一个start,一个end,start指向最大子数组的头部,end指向最大子数组的尾部。初始化让start=0,end=0,都指向a[0].
b.首先找到end的位置,当end指向的是一个正数,直接end++;如果end指向的负数,判断负数右边有没有和比这个负数的绝对值大的数,如果有则让end=i;
c.找到end的位置后,下面去确定start的位置就好确定,只要找出从下标0到end处的所有子数组,中哪个是最大的。

package com.wukung.blog;

/**
 * @author WuKung
 * @csdnURL http://blog.csdn.net/wu_kung/
 * @createdDate 2014-4-10 下午9:34:27
 */
public class MaxSubSequence {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int a[] = { -3, 1, 3, -1, -4, 0, -10, 11, 7, -5 };
		int max = 0;
		int b = 0, s = 0;
		for (int i = 0; i < a.length; i++) {
			if (a[i] >= 0) {
				b = i;
			} else {
				int temp;
				int sum=0;
				for (temp = i; temp < a.length; temp++) {
					sum += a[temp];
					if (sum >= 0) {
						b = i;
						break;
					}
				}
			}
		}
		
		int t = a[b];
		max = a[b];
		s=b;
		for (int i = b - 1; i >= 0; i--) {
			t += a[i];
			if (max <= t) {
				s = i;
				max = t;
			}

		}

		for (int j = s; j <= b; j++) {
			System.out.print(a[j] + " ");
		}

	}
}

思路二：时间复杂度O（n）的算法

其实算法很简单，当前面的几个数，加起来后，b<0后，
把 b 重新赋值，置为下一个元素，b=a[i]。
当 b>sum，则更新 sum=b;
若 b<sum，则 sum 保持原值

package com.wukung.blog;

/**
 * @author WuKung
 * @csdnURL http://blog.csdn.net/wu_kung/
 * @createdDate 2014-4-10 下午11:28:26
 */
public class MaxTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[] a = {-2,3,-1,4,-7,-3,4,5,-2};
		System.out.println("输出最大子数组序列");
		System.out.println(maxSum(a, a.length));
		
	}

	public static int maxSum(int[] a, int n)
	{
		int sum=0;
		int b=0;
		
		int start=0,end=0;
		//针对数组全部为负数的判断。
		int nTemp=a[0];
		for(int j=1; j<n; j++)
		{
			if (nTemp<a[j])
				nTemp=a[j];
		}
		if (nTemp<0)
			return nTemp;
		for(int i=0; i<n; i++)
		{
			if(b<0){
				start=i;
				b=a[i];
				}
			else
				b+=a[i];
			if(sum<b){
				end=i;
				sum=b;
			}
		}
		
		for(int k=start;k<=end;k++){
			System.out.print(a[k]+" ");
		}
		System.out.println();
		System.out.println("输出最大子数组的和：");
		return sum;
	}
}