53. Maximum Subarray - Medium

前往題目

想法

• 這題之前做過，但想不起來方法
• 在想是不是用Sliding window或是Backtracking
• 但中間不能有間隔所以Backtracking沒有意義，我目前做過的題目Backtracking都是因為有時候不需要取中間的items

思路

這題大致有三種解法，最優解是Kadane Algorithm，再來是Divide and conquer和DP，最後是暴力解。

最簡單的是Kadane

1. 只走過一遍array
2. 每個回合的item把它當作是最後一個點，在這之前的總和如果更大就記錄下來
3. 但如果這個總和已經是負數了就歸零，把下一個點當作是起始點
4. 這樣最後就會是maximum

這演算法讓我覺得最神奇的是遇到負數的總和就不要了，但是仔細一想好像是真的，遇到負數的如果不拋棄的話，那就等於說我減去了這個數，倒不如直接不要，還從0開始，比負數大😂

Divide and conquer就是先切半，然後左右兩邊和會經過中間的subarray各自紀錄最大值，最後三個相比，取最大

Code

討論區: Java || Kadane ||Divide and Conquer || Dp

class Solution {
    public int maxSubArray(int[] nums) {
        // The maximum max
        int max = Integer.MIN_VALUE;
        
        // Store each max value of item i
        int currMax = 0;

        // Loop through the array
        for (int i = 0; i < nums.length; ++i) {
            currMax += nums[i];

            // Record the maximum
            max = Math.max(currMax, max);

            // Re init., no negative currMax
            if (currMax < 0) currMax = 0;
        }

        return max;
    }
}

2023/12/05

• 再做一次五分鐘就寫出來但沒考慮到如果只有負數的情況，max賦值以及currMax歸零順序顛倒了，導致max至少都會有0，但如果都是負數答案就不對了