美文网首页
Java 最大子列和问题(Maximum Subsequence

Java 最大子列和问题(Maximum Subsequence

作者: 向祥祥 | 来源:发表于2020-03-30 16:18 被阅读0次

    问题

    给定N个整数序列



    求函数



    的最大值。

    算法一

    算出所有可能的连续子列的和,并比较

    public int MaximumSubsequenceSum1(int[] array,int size) {
        int maxSum=0;
        int tempSum=0;
        for(int i=0;i<size;i++) {
            for(int j=i;j<size;j++) {
                for(int k=i;k<=j;k++) {
                    tempSum+=array[k];
                }
                if(tempSum>maxSum) {
                    maxSum=tempSum;
                }
            }
        }
        return maxSum;
    }
    

    时间复杂度O(N^3)

    算法二

    在解法一的基础上进行改进

    public static int MaximumSubsequenceSum2(int[] array,int size) {
        int maxSum=0;
        int tempSum=0;
        for(int i=0;i<size;i++) {
            tempSum=0;
            for(int j=i;j<size;j++) {
                tempSum+=array[j];
                if(tempSum>maxSum) {
                    maxSum=tempSum;
                }
            }
        }
        return maxSum;
    }
    

    时间复杂度O(N^2)

    算法三

    递归计算:将数组分为两部分,分别计算左、右和包含左右两边元素的三个最大子列和。

    public static int MaximumSubsequenceSum3(int[] array,int size) {
        return MaximumSubsequenceSum3Recursion(array,0,size-1);
    }
    public static int MaximumSubsequenceSum3Recursion(int[] array,int leftIndex,int rightIndex) {
        int maxLeftSum;
        int maxRightSum;
        int maxLeftBorderSum;
        int maxRightBorderSum;
        int tempLeftBorderSum;
        int tempRightBorderSum;
        int centerIndex;
        //传入数组只有一个数时终止
        if(leftIndex==rightIndex) {
            return (array[leftIndex]>=0)? array[leftIndex]:0;
        }
        //分
        centerIndex=(leftIndex+rightIndex)/2;
        maxLeftSum=MaximumSubsequenceSum3Recursion(array,leftIndex,centerIndex);
        maxRightSum=MaximumSubsequenceSum3Recursion(array, centerIndex+1, rightIndex);
        //子列元素在左右两边存在的情况
        maxLeftBorderSum=0;
        tempLeftBorderSum=0;
        for(int i=centerIndex;i>=leftIndex;i--) {
            tempLeftBorderSum+=array[i];
            if(tempLeftBorderSum>maxLeftBorderSum) {
                maxLeftBorderSum=tempLeftBorderSum;
            }
        }
        maxRightBorderSum=0;
        tempRightBorderSum=0;
        for(int i=centerIndex;i<=leftIndex;i++) {
            tempRightBorderSum+=array[i];
            if(tempRightBorderSum>maxRightBorderSum) {
                maxRightBorderSum=tempRightBorderSum;
            }
        }
        return Math.max(maxLeftSum, Math.max(maxRightSum, maxLeftBorderSum+maxRightBorderSum));
    }
    

    时间复杂度O(NlogN)。由于是递归计算,所以空间复杂度较大

    算法四(在线处理)

    public static int MaximumSubsequenceSum3(int[] array,int size) {
        int maxSum=0;
        int tempSum=0;
        for(int i=0;i<size;i++) {
            tempSum+=array[i];
            if(tempSum>maxSum) {
                maxSum=tempSum;
            }else if(tempSum<0) {
                tempSum=0;
            }
        }
        return maxSum;
    }
    

    时间复杂度O(N)

    相关文章

      网友评论

          本文标题:Java 最大子列和问题(Maximum Subsequence

          本文链接:https://www.haomeiwen.com/subject/stmvuhtx.html