最大子序列演算法

最大子序列演算法（Maximum Subsequence Algorithm）是一種用於找出數組中元素的最大子序列的算法。最大子序列問題可以分為最大和子序列和最大連續子序列兩種類型。這裡我們主要討論最大連續子序列問題。

最大連續子序列問題是指在給定數組中找到一個連續子序列，其元素的和最大。例如，給定數組 [23, -11, 45, 2, -1, 6, 7]，其最大連續子序列是 [45, 2, -1, 6, 7]，其和為 59。

最大連續子序列問題可以用動態規劃（Dynamic Programming）來解決。動態規劃的基本思想是定義一個狀態，通過狀態轉移方程來逐步構建最優解。

對於最大連續子序列問題，我們可以定義狀態 f[i] 表示以 a[i] 結尾的最大連續子序列和。狀態轉移方程為：

f[i] = max(f[i-1] + a[i], a[i])

初始時，f[0] = a[0]。

偽代碼如下：

function findMaxSubsequence(a):
    n = length(a)
    f = new array of size n
    f[0] = a[0]
    for i from 1 to n-1:
        f[i] = max(f[i-1] + a[i], a[i])
    return f[n-1]

時間複雜度為 O(n)，空間複雜度為 O(n)。

對於最大子序列問題，如果允許不連續的子序列，則可以使用分治法或貪心算法來解決。例如，Kadane's Algorithm 是一種貪心算法，用於找到給定整數序列中的最大子序列和。它的偽代碼如下：

function findMaxSubarray(a):
    m = 0
    for i from 0 to length(a):
        m = max(m + a[i], a[i])
    return m

時間複雜度為 O(n)，空間複雜度為 O(1)。