Maximum Contiguous Subsequence

最大连续子序列

给定 K 个整数的序列 {N0, N1, …, NK − 1}，其任意连续子序列可表示为 {Ni, Ni + 1, …, Nj}，其中 0 ≤ i ≤ j < K

最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列 {−2, 11, −4, 13, −5, −2}，其最大连续子序列为 {11, −4, 13} ，最大和为 20

编写程序得到其中最大子序列的和并输出该子序列的第一个和最后一个元素的下标

输入格式

输入包含多组测试数据

每组数据占 2 行，第 1 行给出正整数 K

第 2 行给出 K 个整数 N1, …, NK

输出格式

每组数据输出一行结果，包含最大子序列的和以及子序列的第一个下标 i 和最后一个元素的下标 j

所有元素下标为 0 ∼ K − 1

如果最大子序列不唯一，则选择 i 最小的那个子序列，如果仍不唯一，则选择 i 最小的子序列中 j 最小的那个子序列

若所有 K 个元素都是负数，则定义其最大和为 0，输出 0 0 0

数据范围

1 ≤ K ≤ 105, −10000 ≤ Ni ≤ 10000, 输入最多包含 10 组数据

输入样例：

1
2
3
4
5
6
7
8


8
6 -2 11 -4 13 -5 -2 10
5
10 -10 10 -10 10
8
-1 -5 -2 3 -1 0 -2 0
4
-1 -2 -4 -3

输出样例：

分析

last：当前以第 i 个元素结尾的子序列最大和
若 last < 0，则从当前元素重新开始，记录当前左端点 temp
如果当前 last 优于全局最大 res，则更新 res 和左右端点

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


#include <iostream>
#include <climits>

const int N = 100010;
int nums[N];

int main()
{
  int n;

  while (std::cin >> n)
  {
    for (int i = 0; i < n; ++i)
      std::cin >> nums[i];

    int last = 0;                   // 当前子段和
    int res = INT_MIN;             // 最大子段和
    int l = 0, r = 0;              // 结果子序列的起止下标
    int temp = 0;                  // 记录当前子段的起点

    for (int i = 0; i < n; ++i)
    {
      // 如果前缀和为负，丢弃，重开新子段，并记录左端点
      if (last < 0)
        temp = i;

      last = std::max(nums[i], last + nums[i]);

      if (res < last)
      {
        res = last;
        l = temp;                  // 更新起点为当前有效起点
        r = i;                     // 终点为当前下标
      }
    }

    if (res < 0)
      std::cout << "0 0 0" << '\n';  // 所有数都为负数
    else
      std::cout << res << ' ' << l << ' ' << r << '\n';
  }

  return 0;
}