分析求子数组最大值问题

求子数组的最大值是一道经典dynamic programming题，解法如下（参考这里）：

public int maxSubArray(int[] A) {
   int newsum=A[0];
   int max=A[0];
   for(int i=1;i<A.length;i++){
       newsum=Math.max(newsum+A[i],A[i]);
       max= Math.max(max, newsum);
   }
   return max;
}

理解这个算法的关键在于：求出数组中以每个元素为子数组的最后一个元素的最大值（上述代码中newsum），这些最大值中的最大者即为解（上述代码中max）。分析如下：从第一个元素A[0]起，newsum和max均为A[0]。而对下一个元素A[1]，以A[1]为子数组的最后一个元素的最大值或者是A[0]+A[1]（A[0]大于0），或是A[1]，取两者最大值。接下来再看A[2]，以A[2]为子数组的最后一个元素的最大值是A[0]+A[1]+A[2]，A[1]+A[2]和A[2]三者之间的最大值。以此类推。。。