【数据结构与算法】连续子序列最大和——Kadane算法（动态规划思想、贪心策略）

《数据结构实验指导 - C++语言版》题目集 算法1-7~9 连续子序列最大和

题目描述

给定 n 个整数组成的序列，"连续子序列" 被定义为从第 i 个元素到第 j 个元素（包含 i 和 j，且 i≤j）的连续元素组成的序列。"连续子序列最大和" 则是所有可能的连续子序列中元素之和的最大值。

例如，给定序列 - 2, 11, -4, 13, -5, -2，其连续子序列 11, -4, 13 有最大的和 20。

请编写程序，计算给定整数序列的连续子序列最大和，同时输出该子序列首尾的数组下标（从 0 开始）。若解不唯一，则输出最小的数组下标。

注意：如果序列中所有整数皆为零或负数，则取空子列的结果是最大的，为 0；此时空子序列数组首尾的下标均为 - 1。

输入格式

输入第一行给出正整数 n（≤10^5）；第二行给出 n 个整数，绝对值均不超过 100，其间以空格分隔。

输出格式

在第一行中输出连续子序列最大和，第二行输出该子序列首尾的数组下标（从 0 开始），以 1 个空格分隔。

样例输入

10
-10 2 2 3 4 -5 -23 4 7 -21

样例输出

11
1 4

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int max_sum = 0;         // 最大子序列和，初始为0（空子序列）
    int current_sum = 0;     // 当前子序列和
    int start = -1, end = -1;// 最大子序列的首尾下标，初始为-1（空子序列）
    int temp_start = 0;      // 临时记录当前子序列的起始下标

    for (int i = 0; i < n; ++i) {
        // 如果当前子序列和加上当前元素比当前元素还小，就从当前元素重新开始
        if (current_sum + a[i] < a[i]) {
            current_sum = a[i];
            temp_start = i;
        } else {
            current_sum += a[i];
        }

        // 如果当前子序列和大于最大子序列和，更新最大子序列和及下标
        if (current_sum > max_sum) {
            max_sum = current_sum;
            start = temp_start;
            end = i;
        }
    }

    // 输出结果
    cout << max_sum << endl;
    cout << start << " " << end << endl;

    return 0;
}

Kadane 算法

Kadane 算法（最大子数组和算法）主要运用了以下核心思想：

动态规划思想

算法通过维护两个变量（当前子数组和、最大子数组和），在遍历数组时不断更新状态，将原问题分解为 "以当前元素结尾的最大子数组和" 的子问题，利用子问题的解推导出全局最优解。

贪心策略

当当前子数组和为负数时，直接放弃该子数组（重置为 0），从下一个元素重新开始计算。这是因为负数继续累加会导致总和减小，不如从新元素开始计算更优。

局部最优与全局最优结合

每次遍历都比较 "当前子数组和" 与 "全局最大和"，始终保留最大的结果，确保不会错过任何潜在的最优解。

线性扫描优化

算法仅需一次遍历数组（时间复杂度 O (n)），通过常数级别的额外空间实现计算，兼顾了时间和空间效率，尤其适合处理大规模数据（如 10^5 级别的数组）。