CBMS-2019-12

题目来源：[[做题/文字版题库/CBMS/2019#Question 12|2019#Question 12]] 日期：2024-07-26 题目主题：CS-算法-动态规划

解题思路

这个问题要求在一个整数序列中找到一段子序列，使得这段子序列的元素和最大。我们可以使用动态规划的方法来解决这个问题。首先定义一个数组 $t_i$ 表示从 $1$ 到 $i$ 的子序列中，以 $i$ 结尾的最大子序列和。然后，我们可以通过遍历这个数组来计算出整个序列中和最大的子序列。最终算法的时间复杂度是 $O(n)$。

Solution

1. Formula for $t_1$

The formula for $t_1$ is simply the first element of the sequence since it represents the maximum subarray sum ending at the first position:

$$t_1=s_1$$

2. Formula for $t_{i+1}$

To derive $t_{i+1}$ from $t_i$, consider the subarray ending at position $i+1$. There are two possibilities: either the subarray includes only $s_{i+1}$ or it includes the subarray ending at $i$ extended by $s_{i+1}$. Thus:

$$t_{i+1}=\max (t_i+s_{i+1},s_{i+1})$$

This formula captures the choice between starting a new subarray at $i+1$ or extending the previous subarray to include $s_{i+1}$.

3. Algorithm

The algorithm calculates the maximum subarray sum and identifies the starting and ending indices of the subarray that achieves this sum. Here is the algorithm in Python:

def max_subarray_sum(sequence):
    max_sum = current_sum = sequence[1]
    start = end = temp_start = 1
 
    for i in range(2, len(sequence) + 1):
        if current_sum > 0:
            current_sum += sequence[i]
        else:
            current_sum = sequence[i]
            temp_start = i
 
        if current_sum > max_sum:
            max_sum = current_sum
            start = temp_start
            end = i
 
    return start, end, max_sum
 
# Example usage
sequence = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
start, end, max_sum = max_subarray_sum(sequence)
print(f"Maximum subarray sum: {max_sum}")
print(f"Start index: {start}, End index: {end}")

Explanation

• The algorithm initializes the variables max_sum, current_sum, start, end, and temp_start to keep track of the maximum subarray sum and its indices.

• It iterates through the sequence, updating the current_sum based on the formula $t_{i+1}=\max (t_i+s_{i+1},s_{i+1})$.

• If the current_sum is greater than the max_sum, it updates the max_sum, start, and end indices.

• The algorithm returns the start, end, and max_sum values.

Complexity Analysis

• Time Complexity: The algorithm has a time complexity of $O(n)$ since it iterates through the sequence once.

• Space Complexity: The space complexity is $O(1)$ since the algorithm uses a constant amount of space for variables.

知识点

动态规划最大子序列和

难点思路

难点在于理解如何通过比较当前元素和当前子序列和来决定是否开始一个新的子序列或继续当前子序列。理解动态规划的状态转移方程 $t_{i+1}=\max (t_i+s_{i+1},s_{i+1})$ 对于解题至关重要。

解题技巧和信息

1. 动态规划是一种通过分解问题并利用子问题解的技巧。对于本问题，关键在于理解如何通过前一步的解来更新当前解。
2. 对于最大子序列和问题，Kadane’s Algorithm 是一个经典解法，其时间复杂度为 $O(n)$，适合处理大规模数据。

重点词汇

1. subarray 子数组
2. maximum subarray sum 最大子数组和
3. dynamic programming 动态规划
4. sequence 序列

参考资料

1. Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, Chapter 4: Divide-and-Conquer (Maximum Subarray Problem)
2. The Art of Computer Programming, Volume 3: Sorting and Searching by Donald E. Knuth, Section 5.3.2: Maximum Subarray Problem