动态规划--最大子段和

　　最大子段和是一个十分经典的问题。

给定由n个整数（包含负整数）组成的序列a1,a2,...,an，求该序列子段和的最大值。

当所有整数均为负值时定义其最大子段和为0。

例如，当(a1,a2, ……a7,a8)=(1,-3, 7,8,-4,12, -10,6)时，
最大子段和为：23

bj是1到j位置的最大子段和:

…

an-1

|《-------bj--------------》|

由bj的定义易知，当bj-1>0时bj=bj-1+aj，否则bj=aj。

则计算bj的动态规划递归式：

bj=max{bj-1+aj，aj}，1≤j≤n。

	1	2	3	4	5	6
a[i]	-2	11	-4	13	-5	-2
b(初值=0)	-2	11	7	20	15	13
sum	0	11	11	20	20	20

求最大值：

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int MaxSum(int n)
 5 {
 6     int sum = 0;
 7     int b = 0;
 8     for(int i=1; i<=n; i++)
 9     {
10         if(b>0) b+=a[i]; else b=a[i];
11         if(b>sum) sum = b;
12     }
13     return sum;
14 }
15 
16 int main()
17 {
18     
19 }

View Code

构造最优值：

 1 #include<iostream>
 2 using namespace std;
 3 
 4 const int MAXN = 1001;
 5 int a[MAXN];
 6 
 7 int MaxSum(int n, int &besti, int &bestj)
 8 {
 9     int sum = 0;
10     int b = 0;
11     int begin = 0;
12     for(int i=1; i<=n; i++)
13     {
14         if(b>0) b+=a[i];
15         else 
16         {
17             b=a[i]; begin = i;
18         }
19         if(b>sum)
20         {
21             sum = b;
22             besti = begin;
23             bestj = i;
24         }
25     }
26     return sum;
27 }

View Code

当然上面动态规划的算法是最快的算法，时间复杂度为 O(n).

另外还有最直接的解法：暴力算法

实现起来稍微更麻烦的算法：分治算法

暴力解法：时间复杂度O(n^2) 即： P(n, 2) 的运算量

#include <iostream>
using namespace std; 

const int MAXN = 1001; 
int a[MAXN]; 

int MAXSum(int n, int &besti, int &bestj)
{
    int Best_sum = 0;
    int sum = 0; 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
        {
            sum = 0; 
            for (int k = j; k <= i; k++)
                sum += a[k]; 
            if (Best_sum < sum)
            {
                Best_sum = sum; 
                besti = i; 
                bestj = j; 
            }
        }
    return Best_sum; 
}

int main()
{
    int low = 0, high = 0, best_sum = 0; 
    int n; 
    cin >> n; 
    for(int i = 1; i <= n; i++)
        cin >> a[i]; 
    best_sum = MAXSum(n, high, low);

    cout << "From " << low << " to " << high << " is\n"; 
    cout << "the best sum: " << best_sum << endl; 
    
    return 0; 
}

View Code

分治解法：时间复杂度O( nlg(n) )

#include <iostream>
using namespace std; 

const int MAXN = 1010;
int A[MAXN]; 

int findMaxCrossingSubArray(int A[], int low, int mid, int high)
{
    int left_sum = -0x7fffffff; 
    int sum = 0; 
    for (int i = mid; i >= low; i--)
    {
        sum = sum + A[i]; 
        if (sum > left_sum)
        {
            left_sum = sum; 
        }
    }
    
    int right_sum = -0x7fffffff; 
    sum = 0; 
    for (int j = mid + 1; j <= high; j++)
    {
        sum = sum + A[j]; 
        if (sum > right_sum)
        {
            right_sum = sum;  
        }
    }
    return (left_sum + right_sum); 
}

int findMaximumSubArray(int A[], int low, int high)
{
    if (high == low)
    {
        return A[low]; 
    }
    else 
    {
        int mid = (low + high) / 2; 
        int left_sum = findMaximumSubArray(A, low, mid); 
        int right_sum = findMaximumSubArray(A, mid+1, high); 
        int cross_sum = findMaxCrossingSubArray(A, low, mid, high); 
        if (left_sum >= right_sum && left_sum >= cross_sum)
            return left_sum; 
        else if (right_sum >= left_sum && right_sum >= cross_sum)
            return right_sum; 
        else 
            return cross_sum; 
    }
}
int main()
{ 
    int n; 
    cin >> n; 
    for(int i = 1; i <= n; i++)
        cin >> A[i]; 

    int best_sum = findMaximumSubArray(A, 1, n); 
    cout << "the best sum: " << best_sum << endl; 
    
    return 0; 
}

View Code

动态规划--最大子段和

推荐阅读