最大子序列和

一时失言乱红尘 2022-08-04 04:18 191阅读 0赞

# 最大子序列和的4种算法 #

给定整数A1,A2…An(可能有负数)求最大子序列和。（假设所有整数均为负数时，最大子序列和为0）

## Arg1 ##

public int MaxSubsequenceSum(int arr[], int n) {
        int ThisSum, MaxSum;
        MaxSum = 0;
    
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                ThisSum = 0;
                for (int k = i; k <= j; k++)
                    ThisSum += arr[k];
    
                if (ThisSum > MaxSum)
                    MaxSum = ThisSum;
            }
        }
        return MaxSum;
    }

时间复杂度O(N3)

## Arg2 ##

public int MaxSubsequenceSum(int arr[], int n) {
        int ThisSum, MaxSum;
        MaxSum = 0;
    
        for (int i = 0; i < n; i++) {
            ThisSum = 0;
            for (int j = i; j < n; j++) {
    
                ThisSum += arr[j];
    
                if (ThisSum > MaxSum)
                    MaxSum = ThisSum;
            }
        }
        return MaxSum;
    }

时间复杂度O(N2)

## Arg3 ##

分治法的思想，  
“分”：将问题分成两个大致相同的子问题，然后递归的解决  
“治”：将两个子问题的解合并。

在本例中，最大子序列和可能出现在3处：左半部，右半部，占据左右两个部分。  
前两种情况可以递归求解。后一种情况可以通过求出前半部的最大和（包含最后一个元素）以及后半部的最大和（包含第一个元素），然后相加。  
如：4，-3，5，-2，-1，2，6，-2。  
第一种情况的最大和为6（A1-A3）  
第二种情况的最大和为8（A6-A7）  
第三种情况的最大和为11（A1-A7）

public int MaxSubsequenceSum(int arr[], int left, int right) {
    
        int MaxLeftSum, MaxRightSum;
        int MaxLeftBorderSum, MaxRightBorderSum;
        int LeftBorderSum, RightBorderSum;
        int Center, i;
    
        if (left == right) {
            if (arr[left] > 0)
                return arr[left];
            else
                return 0;
        }
    
        Center = (left + right) / 2;
    
        MaxLeftSum = MaxSubsequenceSum(arr, left, Center);
        MaxRightSum = MaxSubsequenceSum(arr, Center + 1, right);
    
        MaxLeftBorderSum = 0;
        LeftBorderSum = 0;
        MaxRightBorderSum = 0;
        RightBorderSum = 0;
    
        for (i = Center; i >= left; i--) {
            LeftBorderSum += arr[i];
            if (LeftBorderSum > MaxLeftBorderSum)
                MaxLeftBorderSum = LeftBorderSum;
        }
        for (i = Center + 1; i <= right; i++) {
            RightBorderSum += arr[i];
            if (RightBorderSum > MaxRightBorderSum)
                MaxRightBorderSum = RightBorderSum;
        }
    
        int max = MaxLeftSum;
        if (MaxRightSum > max)
            max = MaxRightSum;
        if (max < (MaxRightBorderSum + MaxLeftBorderSum))
            max = MaxRightBorderSum + MaxLeftBorderSum;
    
        return max;
    }

时间复杂度O(NlogN).

## Arg4 ##

public int MaxSubsequenceSum(int arr[], int n) {
    
        int ThisSum=0,MaxSum=0;
    
        for(int j=0;j<n;j++){
            ThisSum+=arr[j];
            if(ThisSum>MaxSum)
                MaxSum=ThisSum;
            else if(ThisSum<0)
                ThisSum=0;
        }
    
        return MaxSum;
    }

时间复杂度：线性时间O(N).