- 1、对于一维的情况分析。
- 常规的方法:
- //子数组的最大乘积
- int MaxSum(int *a,int n)
- {
- int maxInt = -10000000;
- int sum = 0;
- if ( n<=0 )
- {
- return 0;
- }
- for ( int i=0;i<n;i++ )
- {
- sum = 0;
- for (int j=i;j<n;j++ )
- {
- sum +=a[j];
- if ( sum>maxInt )
- {
- maxInt = sum;
- }
- }
- }
- return maxInt;
- }
- 但是该方法的效率略差,可以继续优化,具体如下:
- 采用分治法及动态规划的思想,可以将其复杂度降低为O(N)。
- 从数组末尾往前遍历,对于数组A,长度为N,如果已经知道A[i,...,N-1]中和最大的一段数组之和为ALL[i],并且已经知道A[i,...,N-1]中包含A[i]的和最大的一段数组为start[i],那么子数组
- A[i-1,...N-1]最大和即为max(A[i-1],A[i-1]+start[i],ALL[i])具体代码实现如下:
- int maxValue(int x,int y)
- {
- return (x>y)?x:y;
- }
- int MaxSum(int *a,int n)
- {
- //改进后的方法
- int nStart = a[n-1];
- int nAll = a[n-1];
- for (int i=n-2;i>=0;i-- )
- {
- nStart = maxValue(a[i],nStart+a[i]);
- nAll = maxValue(nStart,nAll);
- }
- return nAll;
- }
- //该片段来自于http://www.codesnippet.cn/detail/1908201410258.html
来源: http://www.codesnippet.cn/detail/1908201410258.html