最大子段和c++

最大子段和（Maximum Subarray Problem）是一個經典的動態規劃問題。它的目標是找到一個數列中的最大連續子段和。例如，對於數列 [-2, 11, -4, 13, -5, -2]，最大的子段和是 [11, -4, 13]，其和為 20。

下面是一個使用C++實現的最大子段和算法：

#include <iostream>
#include <vector>

int maxSubArray(const std::vector<int>& nums) {
    // 動態規劃算法，使用數組 dp 來記錄每個子數組的和
    int n = nums.size();
    std::vector<int> dp(n);
    dp[0] = nums[0];
    int maxSoFar = dp[0];

    for (int i = 1; i < n; i++) {
        dp[i] = std::max(nums[i], nums[i] + dp[i - 1]);
        maxSoFar = std::max(maxSoFar, dp[i]);
    }

    return maxSoFar;
}

int main() {
    std::vector<int> nums = {-2, 11, -4, 13, -5, -2};
    std::cout << "The maximum subarray sum is: " << maxSubArray(nums) << std::endl;
    return 0;
}

這個算法的時間複雜度和空間複雜度都是 O(n)，其中 n 是數列的長度。動態規劃算法通過維護一個狀態數組 dp，來記錄每個子數組的和，從而找到全局的最大子段和。

如果你想要找到所有子段和的最大值，而不是僅僅找到一個，你可以使用Kadane's algorithm，它的時間複雜度和空間複雜度都是 O(n)。下面是一個使用Kadane's algorithm的實現：

#include <iostream>
#include <vector>

int findMaxSubArray(const std::vector<int>& nums) {
    int n = nums.size();
    int globalMaxSoFar = nums[0];
    int localMaxEndingAtIndex = nums[0];

    for (int i = 1; i < n; i++) {
        localMaxEndingAtIndex = std::max(nums[i], localMaxEndingAtIndex + nums[i]);
        globalMaxSoFar = std::max(globalMaxSoFar, localMaxEndingAtIndex);
    }

    return globalMaxSoFar;
}

int main() {
    std::vector<int> nums = {-2, 11, -4, 13, -5, -2};
    std::cout << "The maximum subarray sum is: " << findMaxSubArray(nums) << std::endl;
    return 0;
}

這個算法通過維護兩個變數：globalMaxSoFar，用於記錄整個數列的最大子段和；localMaxEndingAtIndex，用於記錄以當前索引結尾的子數組的最大和。在遍歷數列的過程中，不斷更新這兩個變數，最終得到全局的最大子段和。