最大连续子序列的和问题（算法）

ゝ一纸荒年。 2024-04-23 20:13 81阅读 0赞

## 问题描述 ##

给定一个有n（n≥1）个整数的序列，要求求出其中最大连续子序列的和。  
![在这里插入图片描述][bec3476a2caf4e2abe4ba63acf086f75.png]

## 蛮力法 ##

#### 暴力枚举 ####

/**
     * 时间复杂度：O(n^3)
     * @param arr 序列[数组]
     * @param n 数组大小
     * @return int 
     */
    int maxSubSum1(int arr[], int n) {
        
        int thisSum; // 子序列的和
        int maxSum = arr[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;
    }

#### 优化枚举法 ####

暴力枚举存在的问题：  
![在这里插入图片描述][f8b8f5e110a84422b06d9972bc663d43.png]  
使用暴力枚举的时候存在重复计算的情况，可以改进来减少重复计算。  
a\[1,6\] = a\[1,5\] + a\[6\]

![在这里插入图片描述][de977c9da7784889b636bed4bd1d1f0e.png]

// 优化枚举法  时间复杂度：O(n^2)
    int maxSubSum2(int arr[], int n) {
        
        int thisSum; // 子序列的和
        int maxSum = arr[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;
    }

#### 改进的优化枚举法 ####

> 对于 maxSubSum2() 算法，还可以进一步改进。  
> 
> 
>  *  在扫描序列的时候，如果扫描中遇到负数，当前子序列和 thisSum 将会减小，若 thisSum 为负数，表明前面已经扫描的那个子序列可以抛弃了，则放弃这个子序列，重新开始下一个子序列的分析，并置 thisSum 为0。  
>     
>  *  若这个子序列和 thisSum 不断增加，那么最大子序列和 maxSum 也会不断增加。

// 改进的优化枚举法  时间复杂度：O(n)
    int maxSubSum3(int arr[], int n) {
        
        int thisSum = 0; // 子序列的和
        int maxSum = arr[0]; // 最大连续子序列的和
        for(int i = 0;i < n;i++) {
        
            thisSum += arr[i];
            // 若当前子序列的和为负数，就重新开始下一子序列
            if(thisSum < 0) {
        
                thisSum = 0;
            }
            // 比较求最大连续子序列
            if(thisSum > maxSum) {
        
                maxSum = thisSum;
            }
        }
        return maxSum;
    }

--------------------

## 分治法 ##

![在这里插入图片描述][3d0217bd86444f22a08f148672648dc3.png]

> 1.  将数组 a\[0,n-1\] 分解为 a\[0, n/2-1 \] 和 a\[n/2, n-1 \]；
> 2.  递归求解子问题： 左半部分的最大连续子序列和A1=8， 右半部分的最大连续子序列和A2=12
> 3.  合并子问题，得到原问题的最大子序列和。 若跨中点的最大连续子序列和A3； 则原序列的最大连续子序列和为max\{A1,A2,A3\}

求解跨中点的最大子序列的和：

> ![在这里插入图片描述][78e91ccab0d84be681da1763e9f0c071.png]
> 
> 1.  记 mid = n/2 - 1
> 2.  则A3可以分成两个部分：left + right
> 3.  left：以 a\[mid\] 为结尾的最大连续子序列的和；right：以 a\[mid+1\] 为开端的最大连续子序列的和
> 4.  分别求出 left 和 right 即可得到 A3

int getMax(int a, int b, int c) {
        
        int temp = a > b ? a : b;
        int max = temp > c ? temp : c;
        return max;
    }
    
    
    // 分治法  时间复杂度：O(nlogn)
    // left--数组起始下标，right--数组结束下标
    int maxSubSum4(int arr[], int left, int right) {
        
        // 子序列只有一个元素时
        if(left == right) {
        
            if(arr[left] > 0) return arr[left];
            else return 0;
        }
    
        int maxLeftSum = 0, maxRightSum = 0;
        int maxLeftBorderSum = 0, leftBorderSum = 0;
        int maxRightBorderSum = 0, rightBorderSum = 0;
        
        int mid = (left + right)/2;
    
        maxLeftSum = maxSubSum4(arr, left, mid);
        maxRightSum = maxSubSum4(arr, mid+1, right);
    	// 求出以左边加上a[mid]元素构成的序列的最大和
        for(int i = mid;i >= left;i--) {
        
            leftBorderSum += arr[i];
            if(leftBorderSum > maxLeftBorderSum) {
        
                maxLeftBorderSum = leftBorderSum;
            }
        }
    	// 求出a[mid]右边元素构成的序列的最大和
        for(int j = mid+1;j <= right;j++) {
        
            rightBorderSum += arr[j];
            if(rightBorderSum > maxRightBorderSum) {
        
                maxRightBorderSum = rightBorderSum;
            }
        }
        return getMax(maxLeftSum, maxRightSum, maxLeftBorderSum+maxRightBorderSum);
    }

--------------------

## 动态规划 ##

![在这里插入图片描述][aa22bbe44422490a89a83b6676783e64.png]  
可以得到 dp\[j\] 的递推方程：  
![在这里插入图片描述][3be2c391885a4d3288e18d0d91cdd84b.png]  
则序列a的最大连续子序列和等于dp\[j\]（1≤j≤n）中的最大者。

// 动态规划  时间复杂度：O(n)
    // 对于含有n个整数的序列a,设dp[j]表示以a[j]结尾的最大连续子序列和
    int maxSubSum5(int arr[], int n) {
        
        int dp[n];
        dp[0] = arr[0];
        for(int i = 1;i < n;i++) {
        
            if(dp[i-1] > 0) {
        
                dp[i] = dp[i-1] + arr[i];
            } else {
        
                dp[i] = arr[i];
            }
        }
        // 查找dp[]数组中的最大者
        int maxSum = dp[0];
        for(int j = 0;j < n;j++) {
        
            if(dp[j] > maxSum) {
        
                maxSum = dp[j];
            }
        }
        return maxSum;
    }

[bec3476a2caf4e2abe4ba63acf086f75.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/5154bb1904624aba8d2dd9adceefe932.png
[f8b8f5e110a84422b06d9972bc663d43.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/cccc6d5d2d194d1fa001f984c232a227.png
[de977c9da7784889b636bed4bd1d1f0e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/caf4337f7c484b60ae78e555484ca296.png
[3d0217bd86444f22a08f148672648dc3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/b0bec751e7774062a1984f0143bd9538.png
[78e91ccab0d84be681da1763e9f0c071.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/719a36e29aaf4d35b5b4d1bf586ac46b.png
[aa22bbe44422490a89a83b6676783e64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/a8f00b489b034ca08cdb63e582ddb284.png
[3be2c391885a4d3288e18d0d91cdd84b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/d3ed869096154f72a954ad8629c04b90.png