public class LineMaxSubArray 
{
	/**
	*线性时间求解最大子数组问题
	*T(n) = Θ(n)
	*@param arr 传入的数组
	*@param low 数组首元素索引
	*@param high 数组尾元素索引
	*/
	public static int[] findMaxSubArray(int[] arr, int low,int high){
	    int left = 0;          //left:最大子数组左边索引
		int right = 0;         //right:最大子数组右边索引
		int msum = 0;          //msum:最大子数组的和
		int cur = 0;           //cur:子数组的和为正值时的左边索引值（可能的最大子数组的左边索引值）
		int sum = 0;           //sum:以此计算子数组和
        for (int i = 0;i <= high;i++)
        {
            sum += arr[i];
			if (sum > msum)    //当求得当前arr[0,...,i-1]的最大子数组后，遇到的下一个为正数
			{
				msum = sum;
				left = cur;
				right = i;
			}
			                   //也可能下一个为负数，若和不小于零，则不用做任何事
			else if (sum < 0)  //遇到负数并且小于零，则最大子数组不可能以负值开头
			{
				sum = 0;
				cur = i+1;
			}
        }

		return new int[]{left,right,msum};
	}
	
	
	public static void main(String[] args) 
	{
		int[] array = new int[]{13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,-7};
		int[] result = findMaxSubArray(array,0,15);
		System.out.println("left: " + result[0]);
		System.out.println("right: " + result[1]);
		System.out.println("sum: " + result[2]);
	}
}

@@ -290,29 +290,29 @@
 %09int msum = 
-0;   
+-100;
        //msu
@@ -320,16 +320,50 @@
 :%E6%9C%80%E5%A4%A7%E5%AD%90%E6%95%B0%E7%BB%84%E7%9A%84%E5%92%8C
+   %E5%BB%BA%E8%AE%AE%E5%88%9D%E5%A7%8B%E5%80%BC%E5%BA%94%E8%AF%A5%E6%AF%94%E6%95%B0%E7%BB%84%E7%9A%84%E6%9C%80%E5%B0%8F%E5%80%BC%E8%A6%81%E5%B0%8F%EF%BC%8C%E5%A6%82%E6%9E%9C%E5%85%A8%E6%98%AF%E8%B4%9F%E6%95%B0%EF%BC%8C%E5%90%A6%E5%88%99%E4%BC%9A%E5%8F%91%E7%94%9F%E9%94%99%E8%AF%AF
 %0A%09%09int c
@@ -707,13 +707,8 @@
 %0A%09%09%09
-else 
 if (
@@ -743,16 +743,47 @@
 %E4%B8%8D%E5%8F%AF%E8%83%BD%E4%BB%A5%E8%B4%9F%E5%80%BC%E5%BC%80%E5%A4%B4
+   %E8%BF%99%E9%87%8C%E4%B8%8D%E5%BA%94%E8%AF%A5%E6%98%AFelse if %EF%BC%8C%E5%90%A6%E5%88%99%E6%9F%90%E4%BA%9B%E6%83%85%E5%86%B5%E4%B8%8B%E4%BC%9A%E6%9C%89%E6%9C%AA%E7%9F%A5%E9%94%99%E8%AF%AF
 %0A%09%09%09%7B%0A%09%09
@@ -942,59 +942,22 @@
 t%5B%5D%7B
-13,
 -3,-2
-5,20,-3
 ,-1
-6
 ,-2
-3,18,20,-7,12,-5,-22,15,-4,-7
+,-3
 %7D;%0A%09
@@ -1000,10 +1000,9 @@
 y,0,
-15
+4
 );%0A%09

fix 4 LineMaxSubArray.java bug