> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/53.-maximum-subarray-kadane-algo.md).

# 53. Maximum Subarray (kadane-algo

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FMREoPkSDqXOpuHXN2BkV%2Fimage.png?alt=media\&token=a1ed71ba-a77d-4c33-8b3b-f8a4a053efb1)

T: O(n)

S: O(1)

```java
class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int num : nums) {
            sum += num;
            max = Math.max(max, sum);
            if (sum < 0) {
                sum = 0;
            }
        }
        return max;
    }
}
```

```java
class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int num : nums) {
            sum += num;
            max = Math.max(max, sum);
            sum = Math.max(0, sum); // [-1] -> should remain [-1], so put here
        }
        return max;
    }
}
```

or

```java
class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int num : nums) {
            // sum += num;
            // add 後, 如果反而比較小, 就丟棄之前的 sum
            sum = Math.max(sum + num, num); // [-1] -> should remain [-1], so put here
            max = Math.max(max, sum);
            
        }
        return max;
    }
}
```