(1).最大子序列和

(一).最大子序列和

问题描述: 给定一个整型数组，求最大值子序列和。

Example1: 对于输入: -2, 11, -4, 13, -5, -2, 应输出: 20

Example2: 对于输入: -2, -5, -4, -3, -1，应输出: -1

Solution1.

　　最直观也是最暴力的解法:穷举法。

　　在这个算法使用了三重嵌套循环,时间复杂度为O(N³）

 1 int maxSubsequenceSum1(const vector<int> &vec)
 2 {
 3     size_t n = vec.size();
 4     int thisSum, maxSum = vec[0];
 5     for (size_t i = 0; i < n; ++i)
 6         for (size_t j = i; j < n; ++j) {
 7             thisSum = 0;
 8             for (size_t k = i; k <= j; ++k)
 9                 thisSum += vec[k];
10             if (thisSum > maxSum)
11                 maxSum = thisSum;
12         }
13     return maxSum;
14 }

Solution2.

　　在Solution1的解法下，我们发现可以通过去掉一个for循环来优化该算法,将时间复杂度降低为O(N²)

 1 int maxSubsequenceSum2(const vector<int> &vec)
 2 {
 3     size_t n = vec.size();
 4     int thisSum, maxSum = vec[0];
 5     for (size_t i = 0; i < n; ++i) {
 6         thisSum = 0;
 7         for (size_t j = i; j < n; ++j) {
 8             thisSum += vec[j];
 9             if (thisSum > maxSum)
10                 maxSum = thisSum;
11         }
12     }
13     return maxSum;
14 }

Solution3.

　　在第三个算法中，我们将使用递归。这个算法使用了分治(divide-and-conquer)策略，时间复杂度为O(Nlog^N)。

　　　　分治策略的主要思想:

　　　　　　1. 分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。

　　　　　　 2.解决：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。

　　　　　　3.合并：将各子问题的解合并为原问题的解。

　　　　具体到此算法中，最大的子序列和可能出现在三个地方:

　　　　　　1.输入数据的左半部分

　　　　　　2.输入数据的右半部分

　　　　　　3.横跨输入数据的左右部分，从而占据左右两部分

　　　　对于1和2，我们可以递归的解决。

　　　　对于3，需要包含找到左半部分包含最后一个元素的最大子序列和以及右半部份包含第一个元素的最大子序列和，然后将它们相加。

　　举个例子，对于以下输入:

左半部分 | 右半部分

4 -3 5 -2 -1 2 6 -2

　　　　1.左半部分最大子序列和为6。

　　　　2.右半部分最大子序列和为8。

　　　　3.左半部分包含最后一个元素的最大子序列和为4，右半部份包含第一个元素的最大子序列和为7，所以横跨这两部分的最大和为 4+7 = 11。

 1 //divide-and-conquer     helper-function of maxSubsequenceSum3
 2 int maxSubSum(const vector<int> &vec, size_t left, size_t right)  
 3 {
 4     //Base Case
 5     if (left == right)
 6         return vec[left];
 7     //Max Sum
 8     size_t center = (left + right) / 2;
 9     int maxLeftSum = maxSubSum(vec , left , center);
10     int maxRightSum = maxSubSum(vec , center + 1 , right);
11     /*Max Border Sum*/
12     //Left Part
13     int leftBorderSum = 0, maxLeftBorderSum = vec[center];
14     size_t u= center + 1;
15     while (u --> 0) {
16         leftBorderSum += vec[u];
17         if (leftBorderSum > maxLeftBorderSum)
18             maxLeftBorderSum = leftBorderSum;
19     }
20     //Right Part
21     int rightBorderSum = 0, maxRightBorderSum = vec[center + 1];
22     for (size_t i = center + 1; i <= right; ++i) {
23         rightBorderSum += vec[i];
24         if (rightBorderSum > maxRightBorderSum)
25             maxRightBorderSum = rightBorderSum;
26     }
27     return max({ maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum });
28 }
29 
30 int maxSubsequenceSum3(const vector<int> &vec) { return maxSubSum(vec, 0, vec.size() - 1); }

　　在我们的实现中，求左半部分的最大边界和的时候(line12-19)用的while循环，如果我们将代码修改为以下代码是否可行？这个主要是C++语法的问题，与我们的算法没有关系，此处就不详说了。

    for (size_t i = center; i >= left; --i) {
        leftBorderSum += arr[i];
        if (leftBorderSum > maxLeftBorderSum)
            maxLeftBorderSum = leftBorderSum;
    }

Solution4.

　　第4个算法时间复杂度为O(N)

 1 int maxSubsequenceSum4(const vector<int> &vec)
 2 {
 3     size_t n = vec.size();
 4     int thisSum = 0, maxSum = vec[0];
 5     for (size_t i = 0; i < n; ++i) {
 6         thisSum += vec[i];
 7         if (thisSum > maxSum)
 8             maxSum = thisSum;
 9         else if (thisSum < 0)
10             thisSum = 0;
11     }
12     return maxSum;
13 }

　　不难发现为什么这个算法效率如此高:在任意适合算案发对要操作的数据只读取一次，一旦被读取并处理，它就不需要再被记忆了。而在此处理过程中算法能对它已经读入的数据立即给出相应正确答案。（具有这种特点的算法被称为联机算法(on-line algorithms)）

THE END.

相关推荐