C++算法题-最大子列表之和

题目

The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:
Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.
Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.
For example:

1
2


maxSequence({-2, 1, -3, 4, -1, 2, 1, -5, 4});
//should be 6: {4, -1, 2, 1}

code:

1
2
3
4
5


#include <vector>

int maxSequence(const std::vector<int>& arr){
  //...
}

个人题解

注：此法非常麻烦

按照题目来讲如果是空列表返回 0 就好了，这个显而易见。

对于如何求最大的子列表，这个子列表可以从单独一个元素到完整的母列表，都是可能的。那么或许将全部子列表都拉出来求和进行判断可能是最简单的办法了。
不过这种办法需要三层循环(不使用一些取巧的内置函数的情况下。)
首先前置操作：记录最大值，判断特殊条件，

1
2


    long max = 0;
    if (arr.empty()) return 0;

三层循环，首先第一层是当前求和的元素数。求和的元素可能只有一个，也可能是一整个母列表个数。不过为了方便后续第二层循环，初始值为 0。

1

    for (int i = 0; i < arr.size(); i++) {          // 求和行数

第二层定起点位置，注意每次遍历到后面可别超过最后一个元素了，不然列表指针指向虚无可不是开玩笑的（
为了防止这种情况发生，循环条件应该要 < arr.size() - i

1

        for (int j = 0; j < arr.size() - i; j++) {  // 位置

并且提供一个变量以供求和。
之后就是第三层循环求和，这里还要 +1 是因为前面初始化 i 偷懒（

1

            for (int k = j; k < j + i + 1; k++) sum += arr[k];

最后进行比较:

1

            if (sum > max) max = sum;

总的代码长这样

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


int maxSequence(std::vector<int> arr) {
    long max = 0;
    if (arr.empty()) return 0;

    for (int i = 0; i < arr.size(); i++) {
        for (int j = 0; j < arr.size() - i; j++) {
            long sum = 0;
            for (int k = j; k < j + i + 1; k++) sum += arr[k];
            if (sum > max) max = sum;
        }
    }

    return max;
}

他人题解

Kadane 算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


#include <vector>

using namespace std;

int maxSequence(const vector<int>& arr) {
	int localmax=0;
	int globalmax=0;
	for (int i = 0;i<arr.size();i++)
	{
		localmax = localmax + arr[i];
		if (localmax > globalmax)
			globalmax = localmax;
		if (localmax < 0)
			localmax = 0;
	}
	return globalmax;
}

只使用一个循环就能够完成题目，实在巧妙!!!
实际上，只要能保持 localmax 一直为正并在其突破 globalmax 后将 globalmax 赋值为 localmax 这样也可以保证最终得到最大数。如果想到这里就压根不需要三层循环将自己脑袋转冒烟❤️‍🔥

C++ 内置 max() 函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


#include <vector>
#include <numeric>

int maxSequence(const std::vector<int>& arr)
{
    int max = 0;

    for (size_t i = 0; i < arr.size(); i++)
      for (size_t j = i; j < arr.size(); j++)
          max = std::max(std::accumulate(arr.begin() + i, arr.begin() + j + 1, 0), max);
    return (max);
}

这里 i 是位置， j 是子字符串长度。
std::accumulate() 函数的模板如下:

1

    std::accumulate(InputIterator first, InputIterator last, Tp init)

前两个参数规定范围， init 规定初始值，以后就在 fitst ~ last 返回在 init 的基础上累加。
arr.begin() + j + 1 中，加 j 很好理解，而 + 1 是规定最开始一个元素。
std::max() 比较好理解，比较两个参数返回最大的那个。
和我的代码一样，两层 for 循环可以列举出所有可能的子列表，但是他这个就更容易理解。

还有一种含 std::max() 的答案，不过其实是 Kadane 算法的变形:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


#include <vector>

using namespace std;

int maxSequence(const vector<int>& arr) noexcept {
  int max = 0, local = 0;
  for (auto x : arr) {
    local = std::max(0, x + local);
    max = std::max(max, local);
  }
  return max;
}