一个有N个整数元素的一维数组{A[0],A[1],....,A[N-1],A[N]},这个数组有很多子数组,那么子数组之和的最大值是什么?
先给出一个时间复杂度为O(N^2)的求解程序实现,思想很简单,就是遍历数组中所有的子数组,代码如下:
/** * 计算数组的最大子序列 * @author win7 * */ public class MaxSubArraySum { public static int sumN2(int [] array){ int sum=0,maxSum=Integer.MIN_VALUE; int n=array.length; int count=0; for(int i=0;i<n;i++){ sum=0; for(int j=i;j<n;j++){ sum+=array[j]; if(sum>maxSum){ maxSum=sum; } count++; } } System.out.println("length="+n+"||count="+count); return maxSum; } public static void main(String [] args){ // System.out.println("MIN_VALUE="+Integer.MIN_VALUE); int [] array={-5,-2,-3,-5,-3,-2}; int sum=MaxSubArraySum.sumN2(array); System.out.println("最大子序列和="+sum); } }
因为子数组求和满足动态规划的后无效特性,所以可以使用动态规划的思想,从分治的算法中得到提示:可以考虑数组的第一个元素A[0],以及最大的一段数组(A[i],...A[j])跟A[0]之间的关系,有一下几种情况:
1.当0=i=j时,元素A[0]元素本身构成和最大的一段;
2.当0=i<j时,和最大的一段以A[0]开始;
3.当0<i时,元素A[0]跟和最大的一段没有关系。
从上面的三种情况可以将一个大问题(N个元素的数组)转化为一个较小的问题(n-1个元素的数组)。假设知道(A[1],...,A[N-1])中包含A[1]的和最大的一段的和为start[1]。那么,根据上面分析的三种情况,不难看出(A[0],...,A[N-1])中问题的解all[0]是三种情况的最大值max{A[0],A[0]+start[1],all[1]}。通过问题分析,可以看到问题满足无后效性,可以使用动态规划的方法来解决。
程序代码实现如下:
/** * 在时间复杂度为O(N)内找出数组中最大的子序列的累加和 * @param array * @return */ public static int sumN(int [] array){ int n=array.length; int all=array[n-1],start=array[n-1]; int count=0; for(int i=n-2;i>=0;i--){ if((start+array[i])>array[i]){ start=start+array[i]; }else{ start=array[i]; } if(all<start){ all=start; } count++; } System.out.println("数组长度="+array.length+"||时间复杂度="+count); return all; }