# 53. Maximum Subarray

## Description

See description at <https://leetcode.com/problems/maximum-subarray/>

## Solutions

### Kadane's Algorithm

See [Kadane's Algorithm](#kadanes-algorithm). This is a slight modification of Kadane's algorithm in that it allows for an input array of all negatives (example: nums = \[-5, -3, -7, -2, -4]. The result in this case will be -3. The input array is also assumed to have at least one value.

```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        current_sum = nums[0]
        high_sum = current_sum
        for i in range(1, len(nums)):
            current_sum = max(nums[i], current_sum + nums[i])
            high_sum = max(current_sum, high_sum)
            
        return high_sum
```

### My Solution

I was on the right track to the optimal solution which is Kadane's Algorithm. I should have taken extra time to look at my nested if statements. I knew it was bad, but just submitted anyway. If I stopped and looked closer, I think I could have simplified it closer to Kadane's Algorithm. I was happy I found the O(N) solution.

```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        current_sum = nums[0]
        high_sum = current_sum
        for i in range(1, len(nums)):
            if current_sum < 0:
                if nums[i] > 0:
                    current_sum = nums[i]
                else:
                    current_sum = max(current_sum, nums[i])
            else:
                current_sum += nums[i]
            high_sum = max(current_sum, high_sum)
            
        return high_sum
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://monica-granbois.gitbook.io/cs-theory-and-problems/problems/leetcode/53.-maximum-subarray.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.