頭腦風暴：最大子序和

題目

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。

示例：

輸入: [-2,1,-3,4,-1,2,1,-5,4] 輸出: 6

解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。

解題思路

根據題意，本題可使用動态規劃的方式來求解。

第一步，确定dp數組以及下标的含義：

dp[i]：包括下标i之前的最大連續子序列和為dp[i]。

第二步，确定遞推公式：

dp[i] 當且僅有兩個方向可以推斷：

1. dp[i - 1] + nums[i]，即：nums[i]加入目前連續子序列和
2. nums[i]，即：從頭開始計算目前連續子序列和

第三步，dp 初始化:

根據dp[i]的定義, dp[0] = nums[0]。

第四步，确定周遊順序：

遞推公式中dp[i]依賴于dp[i - 1]的狀态，需要從前向後周遊。

代碼實作

public static int maxSubArray(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int res = nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            res = res > dp[i] ? res : dp[i];
        }
        return      

最後

• 時間複雜度：O(n)
• 空間複雜度：O(n)

我是傑少，如果您覺的我寫的不錯，那請給我 點贊+評論+收藏 後再走哦！

1. 閱讀完記得給我點個贊哦，有👍 有動力
2. 關注公衆号---HelloWorld傑少，第一時間推送新姿勢