「PAT甲级真题解析」Advanced Level 1007 Maximum Subsequence Sum

Table of Contents

问题分析

题设给定一组序列, 要求最大的子序列和. (子序列是要求数在原数字中位置连续, 而子数组不要求)。 理论上, 我们只要枚举出所有的子序列进行求和, 然后记录和最大的一组即可。

如何避开肯定不是和最大的子序列

  1. 为了最大, 正值元素越多越好。所以开头元素必须选择正数, 否则选择子序列中的第一个正值元素作为开头就可以得到和更大子序列。
  2. 由于在选择子序列的时候, 是先"选定子数列最左边元素", 然后不断选择"是否将右边元素加入到子序列"中。 所以如果一个子序列"1 2 3 4"结束选择之后, 下一个序列首元不应该选择首元之后的其他元素（"2", "3", "4"）作为新的子序列首元。
  3. 如果当前序列和为负数, 等价于选择了一个负值作为首元的情况, 应该结束当前这轮子序列的选择, 重新开始一轮选择.

完整描述步骤

  1. 获取输入: 数值个数, 给定数列
  2. 初始化计数器:
    • 当前子序列和 = 0
    • 当前子序列起始位置
    • 当前和最大的子序列的和 = -1, 起始位置 = 0, 结束位置 = 给定数列末尾位置
  3. 从第一个元素开始:
    • 计算当前和
    • 如果当前和大于当前最大和:
      • 更新当前最大和为当前和
      • 更新和最大子序列的起始位置和结束位置
    • 如果当前和小于0, 则结束当前子序列的处理:
      • 更新当前子序列的起始位置为下一个位置（意味着开始新一轮的选择）
      • 更新当前子序列的和为0
  4. 输出最大和（如果最大和是初始负数值, 则输出0）, 起始位置, 结束位置

伪代码描述

  1. get input: number_amount, numbers
  2. init recorder:
    • current_sum = 0;
    • current_start_index = 0;
    • max_sum = 0;
    • start_index = 0, end_index = len(numbers) - 1;
  3. for index in range(0, len(numbers)):
    • current_sum += numbers[index]
    • if current_sum > max_sum:
      • current_sum = max_sum;
      • start_index = current_start_index;
      • end_index = index;
    • elif current_sum < 0:
      • start_index = i + 1;
      • current_sum = 0;
  4. if max_sum < 0: print(0)
    • else: print(max_sum)

完整提交代码

1/*
2# 问题分析
3题设给定一组序列, 要求最大的子序列和. (子序列是要求数在原数字中位置连续, 而子数组不要求)。
4理论上, 我们只要枚举出所有的子序列进行求和, 然后记录和最大的一组即可。
5
6# 如何避开肯定不是和最大的子序列
71. 为了最大, 正值元素越多越好。所以开头元素必须选择正数, 
8否则选择子序列中的第一个正值元素作为开头就可以得到和更大子序列。
92. 由于在选择子序列的时候, 是先"选定子数列最左边元素", 然后不断选择"是否将右边元素加入到子序列"中。
10所以如果一个子序列"1 2 3 4"结束选择之后, 下一个序列首元不应该选择首元之后的其他元素（"2", "3", "4"）作为新的子序列首元。
113. 如果当前序列和为负数, 等价于选择了一个负值作为首元的情况, 应该结束当前这轮子序列的选择, 重新开始一轮选择.
12
13# 完整描述步骤
141. 获取输入: 数值个数, 给定数列
152. 初始化计数器:
16    - 当前子序列和 = 0
17    - 当前子序列起始位置
18    - 当前和最大的子序列的和 = -1, 起始位置 = 0, 结束位置 = 给定数列末尾位置
193. 从第一个元素开始:
20    - 计算当前和
21    - 如果当前和大于当前最大和:
22        - 更新当前最大和为当前和
23        - 更新和最大子序列的起始位置和结束位置
24    - 如果当前和小于0, 则结束当前子序列的处理:
25        - 更新当前子序列的起始位置为下一个位置（意味着开始新一轮的选择）
26        - 更新当前子序列的和为0
274. 输出最大和（如果最大和是初始负数值, 则输出0）, 起始位置, 结束位置
28
29# 伪代码描述
301. get input: number_amount, numbers
312. init recorder:
32    - current_sum = 0;
33    - current_start_index = 0;
34    - max_sum = 0;
35    - start_index = 0, end_index = len(numbers) - 1;
363. for index in range(0, len(numbers)):
37    - current_sum += numbers[index]
38    - if current_sum > max_sum:
39        - current_sum = max_sum;
40        - start_index = current_start_index;
41        - end_index = index;
42    - elif current_sum < 0:
43        - start_index = i + 1;
44        - current_sum = 0;
454. if max_sum < 0: print(0)
46    - else: print(max_sum)
47    
48
49*/
50
51#include <iostream>
52#include <vector>
53using namespace std;
54
55int main()
56{
57    int number_amount;
58    cin >> number_amount;
59    vector<int> numbers(number_amount);
60    int max_sum = -1, start_index = 0, end_index = number_amount - 1;
61    int current_start_index = 0, current_sum = 0;
62    for (int i = 0; i < number_amount; i++)
63    {
64        scanf("%d", &numbers[i]);
65        current_sum += numbers[i];
66        if (current_sum < 0)
67        {
68            current_sum = 0;
69            current_start_index = i + 1;
70        }
71        else if (current_sum > max_sum)
72        {
73            max_sum = current_sum;
74            start_index = current_start_index;
75            end_index = i;
76        }
77    }
78    if (max_sum < 0)
79        max_sum = 0;
80    cout << max_sum << " " << numbers[start_index] << " " << numbers[end_index] << endl;
81
82    return 0;
83}
84
Mastodon