最大子序和c++

最大子序和（Maximum Subarray Problem）是一個經典的動態規劃問題，它的目標是找出一個數組中的最大連續子序列和。這個子序列不需要是連續的，但它的元素必須是連續的。

例如，對於數組 [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]，它的最大子序和是 [20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]，其和為 33。

在C++中，我們可以使用動態規劃來解決這個問題。動態規劃算法的基本思想是，通過定義狀態來找出最優解。在這個問題中，我們可以定義狀態 dp[i] 表示以 A[i] 結尾的最大子序列和。

下面是一個使用動態規劃解決最大子序和問題的C++代碼示例：

#include <iostream>
#include <vector>

int findMaxSubArray(const std::vector<int>& array) {
    int n = array.size();
    if (n == 0) return 0;

    // 定義狀態 dp[i] 表示以 A[i] 結尾的最大子序列和
    std::vector<int> dp(n);

    // 初始化 dp[0] 為 A[0]，其他為 0
    dp[0] = array[0];
    for (int i = 1; i < n; ++i) {
        dp[i] = std::max(dp[i - 1] + array[i], array[i]);
    }

    // 返回整個數組的最大子序列和
    return *std::max_element(dp.begin(), dp.end());
}

int main() {
    std::vector<int> array = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
    int maxSubArraySum = findMaxSubArray(array);
    std::cout << "The maximum subarray sum is: " << maxSubArraySum << std::endl;
    return 0;
}

在這個代碼中，我們首先定義了一個函式 findMaxSubArray，它接受一個整數數組作為參數，並返回整個數組的最大子序列和。我們使用了一個輔助數組 dp 來存儲狀態，並通過循環來計算 dp[i] 的值。最後，我們返回 dp 中的最大值。

請注意，這個算法的時間複雜度和空間複雜度都是 O(n)，其中 n 是數組的大小。