求最大子数组之和

求最大子数组之和的线性解法：本算法受编程珠玑中提示而得

/**
	 * 线性时间复杂度求最大和子数组
	 * @param a 源数组
	 * @return  结果数组 长度为3的数组  分别为元素起始位置 结束位置 总和
	 */
	public static int[] getMaxSumSubArray(int a[])
	{
		int begin = 0,end = -1,maxSofar = 0,maxHere = 0,cbegin = 0,cend=-1;
		
		for(int i=0;i<a.length;i++)
		{
			maxHere += a[i];
			if(maxSofar<maxHere)
			{
				maxSofar = maxHere;
				begin = cbegin;
				end = cend;
			}
			
			if(maxHere < 0)
			{
				maxHere = 0;
				cbegin = i+1;
				cend = -1;
			}
			else 
			{
				cend = i+1;
			}
				
		}
		System.out.println("begin  end  sum");
		System.out.println(begin+"  "+end+"  "+maxSofar);
		return new int[]{begin,end,maxSofar};
	}