Maximum Consecutive Subsequence(最大連續子序列-找出總和最大且長度為 k 的連續子序列)

背景介紹

在解決問題時，我們經常會遇到需要找出陣列中特定長度的連續子序列，並求出其總和或總乘積的情況。接下來幾篇文將介紹如何設計三種不同情況下的演算法，分別是：

1. 找出總和最大且長度為 k 的連續子序列。

2. 找出總和最大且長度不大於 k 的連續子序列。

3. 找出總乘積最大的連續子序列。

在本文中，我們將透過數學歸納法的方式，逐步設計出滿足要求的演算法，並使用pseudo code和示例對其進行說明。

1. 總和最大且長度為 k 的連續子序列

1.1 數學歸納法思路

我們將使用數學歸納法來設計演算法。首先，我們需要定義一些變數：

• max_sum：存儲目前找到的最大子序列的和。
• max_start_index：存儲找到的最大子序列的起始索引。
• current_sum：存儲當前遍歷的 k 長度子序列的和。

然後，我們進行歸納：

假設：我們已經知道如何在大小小於 n 的序列中找到滿足條件的連續子序列。

歸納：

• current_sum：在遍歷過程中，我們每次只需要將當前元素加入到 current_sum 中，並減去窗口最左端的元素，以保持窗口長度為 k。即 current_sum = current_sum + X[n] - X[n-k]。
• max_sum：如果 current_sum 大於 max_sum，則更新 max_sum 和 max_start_index。

1.2 演算法描述

Algorithm Maximum_Consecutive_Subsequence(X, n, k):
    Input: X (長度為 n 的陣列), k (子序列長度)
    Output: 最大總和的連續子序列
    
    max_sum = 負無窮大
    max_start_index = -1
    current_sum = 0
    
    for i from 0 to k-1 do
        current_sum += X[i]
        
    max_sum = current_sum
    max_start_index = 0
    
    for i from k to n-1 do
        current_sum += X[i] - X[i - k]
        
        if current_sum > max_sum then
            max_sum = current_sum
            max_start_index = i - k + 1
    
    return X[max_start_index : max_start_index + k]

1.3 示例說明

讓我們以序列 (3, -5, 8, -2, -3, 1, -2, 1, 8, -4, 3) 為例，找出長度為 5 的總和最大連續子序列。

1. 我們首先呼叫 Maximum_Consecutive_Subsequence 函式，傳入參數 X = (3, -5, 8, -2, -3, 1, -2, 1, 8, -4, 3)，n = 11，k = 5。
2. 初始化變數：max_sum = 負無窮大，max_start_index = -1，current_sum = 0。
3. 第一個迴圈：考慮前 5 個元素 (3, -5, 8, -2, -3)，計算它們的和 current_sum。
4. 第二個迴圈：從索引 5 開始，遍歷原始序列。依次計算以每個元素為末尾的長度為 5 的子序列的和，並更新 max_sum 和 max_start_index。
5. 返回最大子序列：從原始序列中取出 max_start_index 到 max_start_index + k 的元素，即為最大總和連續子序列。

最終結果為 [-2, 1, 8, -4, 3]。