分析求子数组最大值问题

求子数组的最大值是一道经典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]起,newsummax均为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]三者之间的最大值。以此类推。。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.