现在的位置: 首页 > 综合 > 正文

求数组的子数组之和的最大值

2014年01月16日 ⁄ 综合 ⁄ 共 1381字 ⁄ 字号 评论关闭

   一个有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;
    }




抱歉!评论已关闭.