> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/01-22-2022-53.md).

# 01/22/2022 53

1. brutal force.  time o(n^2) space: o(1)

<pre class="language-java"><code class="lang-java">class Solution { 
    public int maxSubArray(int[] nums) {
        // brutal force
        int maxSum = Integer.MIN_VALUE;
        
        for (int i = 0; i &#x3C; nums.length; i++){
            <a data-footnote-ref href="#user-content-fn-1">int sum = 0;</a> // important
            for (int j = i; j &#x3C; nums.length; j++){
                sum += nums[j];
                maxSum = Math.max(sum, maxSum);
            }
        } 
        return maxSum;
        
        }
}
</code></pre>

use Kadane's Algorithm, set the sum and max both to the first element of the array. Then iterate from the second element, set sum with the bigger value of nums\[i], and sum + nums\[i], and set max with bigger value of max and sum.

Time O(n)

Space O(1)

```
class Solution { 
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++){
            sum += nums[i];
            maxSum = Math.max(maxSum, sum);

            if (sum < 0){
                sum = 0;
            }
        }
        return maxSum;
    }
}

```

```
```

[^1]: