编程题 01-复杂度1 最大子列和问题【PAT】

编程练习题目集目录

题目

  给定K个整数组成的序列 { N 1 ， N 2 ， . . . ， N k } \{N_1，N_2，...，N_k\} {N1​，N2​，...，Nk​}，“连续子列”被定义为 { N i ， N i + 1 ， . . . ， N j } \{N_i，N_{i+1}，...，N_j\} {Ni​，Ni+1​，...，Nj​}，其中 $1\le i\le j\le K$。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列 { − 2 , 11 , − 4 , 13 , − 5 , − 2 } \{ -2, 11, -4, 13, -5, -2\} {−2,11,−4,13,−5,−2}，其连续子列 { 11 , − 4 , 13 } \{ 11, -4, 13\} {11,−4,13} 有最大的和 $20$。现要求你编写程序，计算给定整数序列的最大子列和。
  本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

• 数据 $1$：与样例等价，测试基本正确性；
• 数据 $2$：$10^2$ 个随机整数；
• 数据 $3$：$10^3$ 个随机整数；
• 数据 $4$：$10^4$个随机整数；
• 数据 $5$：$10^5$ 个随机整数；

输入格式

  输入第 $1$ 行给出正整数 $K（\le 100000）$；第 $2$ 行给出 $K$ 个整数，其间以空格分隔。

输出格式

  在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出 $0$。

输入样例

6
-2 11 -4 13 -5 -2

输出样例

20

题解

解题思路

  分而治之：时间复杂度 $O（O(nlogn）$，空间复杂度 $O（logn）$（递归栈），较高效但更复杂。将序列分成两部分，分别求出左半部分和右半部分的最大子列和，然后求出跨越中间的最大子列和，最后返回这三者中的最大值。左半部分和右半部分可以递归地继续划分下去，直到序列长度为 $1$ 时，其最大子列和即为序列本身元素（如果该元素为正数，否则为 $0$）。
  动态规划：时间复杂度 $O（n）$，空间复杂度 $O（1）$，最高效。用一个数组 $dp$ 来保存前 $i$ 个元素的最大子列和，$dp[i]$ 等于 $max(dp[i-1]+A[i],A[i])$，因为如果前 $i-1$ 个元素的最大子列和加上第 $i$ 个元素大于第 $i$ 个元素本身，那么最大子列和就是这个和，否则就是第 $i$ 个元素本身。最终的最大子列和就是 $dp$ 数组中的最大值。
  贪心算法：时间复杂度 $O（n）$，空间复杂度 $O（1）$，与动态规划效率相同但实现方式不同。维护一个当前和 $cur\_sum$，遍历序列中的每个元素，将当前元素加到 $cur\_sum$ 上，如果 $cur\_sum$ 大于 $max\_sum$（初始为 $0$），则更新 $max\_sum$；如果 $cur\_sum$ 小于等于 $0$，则将 $cur\_sum$ 重置为 $0$，重新开始计算新的子列和。

完整代码

// 分而治之：
#include <iostream>
using namespace std;


int MaxSubSum(int A[], int left, int right) {
    int max_sum = 0;

    if (left == right) {            // 如果子数组只有一个元素，直接返回该元素（如果为正数）或0（如果为负数）
        if (A[left] > 0)
            max_sum = A[left];
        else
            max_sum = 0;
        return max_sum;
    }

    int mid = (left + right) / 2;                        // 计算中间索引
    int left_max_sum = MaxSubSum(A, left, mid);     // 递归计算左半部分和右半部分的最大子序列和
    int right_max_sum = MaxSubSum(A, mid + 1, right);
    int left_s = 0, left_ms = 0;                        // 初始化左右两部分的当前和与最大和
    for (int i = mid; i >= left; i--) {                 // 从中间向左边扫描，计算跨越中间的最大子序列和
        left_s += A[i];
        if (left_s > left_ms)
            left_ms = left_s;
    }
    int right_s = 0, right_ms = 0;
    for (int i = mid + 1; i <= right; i++) {            // 从中间向右边扫描，计算跨越中间的最大子序列和
        right_s += A[i];
        if (right_s > right_ms)
            right_ms = right_s;
    }
    int cross_max_sum = left_ms + right_ms;             // 计算跨越中间的最大子序列和
    return max(max(left_max_sum, right_max_sum), cross_max_sum);         // 返回三者中的最大值
}

int main(void) {
    int K;
    cin >> K;
    int A[K];
    for (int i = 0; i < K; i++) {
        cin >> A[i];
    }
    cout << MaxSubSum(A, 0, K - 1) << endl;
    return 0;
}

// 动态规划：
#include <iostream>
using namespace std;

int main(void) {
    int K;
    cin >> K;
    int A[K];
    for (int i = 0; i < K; i++) {
        cin >> A[i];
    }
    int dp[K];                          // 动态规划数组
    dp[0] = max(A[0], 0);          // 初始化第一个元素
    int max_sum = dp[0];                // 当前最大子序列和
    for (int i = 1; i < K; i++) {       // 填充动态规划数组
        dp[i] = max(dp[i - 1] + A[i], A[i]);
        if (dp[i] > max_sum) {
            max_sum = dp[i];
        }
    }
    cout << max_sum << endl;
    return 0;
}

// 贪心算法：
#include <iostream>
using namespace std;

int main(void) {
    int K;
    cin >> K;
    int A[K];
    for (int i = 0; i < K; i++) {
        cin >> A[i];
    }
    int max_sum = 0, cur_sum = 0;
    for (int i = 0; i < K; i++) {       // 遍历数组，使用贪心算法计算最大子序列和
        cur_sum += A[i];
        if (cur_sum > max_sum) {
            max_sum = cur_sum;
        }
        if (cur_sum < 0) {
            cur_sum = 0;
        }
    }
    cout << max_sum << endl;
    return 0;
}