# maxSubArray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

**Example:**

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

[Question link](https://leetcode.com/problems/maximum-subarray/)

## What are our inputs?
- integer array `nums` <--- An input
- Must contain at least one number <--- A constraint we can work with
- *contiguous* <--- A constraint we can work with
- This means that the numbers have to be next to each other

## What is our task?
- Return the sum
- Sum of the largest contiguous subarray
**Note:** we don't need to return the largest continguous subarray. Without first defining what we need, it's easy to get trapped thinking we need to return the contiguous subarray.

## Thought Process
What are some examples that I can think about?

1. Given example.
2. Come up with some edge cases.

### Given Example
At this point I'm just playing with the constraints and seeing how things play out.

How would I find the sum of the largest continugous subarray?

-2,1,-3,4,-1,2,1,-5,4

Well, could I keep two pointers? One pointing at the start and one pointing at the end of the continguous subarray?

Then at each step I would move one pointer and keep the bigger sum of either pointer.

Let's try

move end pointer
-2 + 1 = -1 vs -2 + 1 + -3 = -4
-2 + 1 = -1

move end pointer
-2 + 1 = -1 vs -2 + 1 + -3 + 4 = 0
keep -2 + 1 + -3 + 4 = 0

move beginning pointer
-2 + 1 + -3 + 4 = 0 vs 1 + -3 + 4 = 2
keep 1 + -3 + 4 = 2

move end pointer
1 + -3 + 4 = 2 vs 1 + -3 + 4 + -1 = 2 
keep 1 + -3 + 4 - 1 = 2 

move beginning pointer
1 + -3 + 4 + -1 = 2 vs -3 + 4 + -1 = 0
keep 1 + -3 + 4 - 1 = 2

### Conclusion of Given Example

At this point I'm realizing there's no method to my madness. Sometimes I'm moving the beginning pointer. Sometimes I'm moving the end pointer. I think it's b/c really my hypothesis presents 2 possibilities at every step. Resulting in an almost tree like structure:

                        (-2, 1) 
                        /      \
                (-2,1,-3)        (1)
                /        \          \
        (-2,1,-3,4)      (1, -3)    (1, -3)
            /   \       /      \        /   \     
(-2,1,-3,4,-1)(1,-3,4)(1,-3,4)(-3)  (1,-3,4)(-3)

(In retrospect the repetative nature of the tree could have been very helpful evidence that this problem had a possibility of a dynamic programming nature. Unfortunately I decided not to draw out the entire tree... I drew something similar, but it wasn't as clear as this. I don't think what I drew wouldn't have been particularly helpful)

At this point I didn't have evidence that this problem was a dynamic programming problem, but it felt very much like a problem I did previously. It was a dynamic programming problem, which I may cover in another set of notes.

### Edge Example 1

The given example had allowed me to get a feel for the problem. Now I wanted to see if I could push the constraints of the problem and utilize those constraints.

I came up with two examples:

Example 1
+5 -1 -1 -1 -1 +5

Example 1 allowed me to see that I would need to sum up the entire array in order to get the answer. There was no getting around that.

I tried to see if I could find the answer by keeping **a running sum** and comparing with **the maximum number seen so far**.

Numbers in the array
+5        -1         -1         -1         -1         +5

5     5 vs 4     5 vs 3     5 vs 2      5 vs 1    6 vs 6
Maximum seen so far vs Running Sum

Ok so I can find the sum of the largest contiguous subarray for this example.

But I knew this would fail in another example, so I wanted to see what was causing the error.

### Edge Example 2
Let's try the same method with a second example.

Example 2
+3  -1    -1   -1    -1   +2   -1 +5

I chose this example b/c the largest continguous subarray was not the entire array so the running sum would fail.

To clearly see

Example 2
+3  -1    -1   -1    -1   +2    -1    +5

3  3vs2  3vs1  3vs0 3vs-1 3vs1 3vs0  3vs5

The solution is 6.

What is the problem? (This would have been the best question to ask in retrospect, but instead I decided to go off and waste a lot of time thinking about a 2D solution which didn't make much sense. I dismissed this path b/c of a problem without understanding what the problem was.)

The problem here is when a better start appears. If we had done started the subarray at 2...

+3  -1    -1   -1    -1   +2    -1    +5

3  3vs2  3vs1  3vs0 3vs-1 3vs2 3vs1  3vs6
                            
                    Note: 3vs2 

It would have worked.

### Would this work in general?

Consider example 1:
At any moment we are comparing two things:
1.1. the max sum of the largest contiguous subarray we've seen so far
1.2. the running sum

In example 1, sum of the largest contiguous subarray happened to be equal to the running, which is why it worked.

In example 2, the method failed b/c the sum of the largest contiguous subarray is no longer equal to the running sum. The **better place to start** the contiguous subarray would be at the +2. So we throw away the running sum.

Consider example 2:

At any moment we are comparing two things:
2.1. the sum of the largest contiguous subarray we've seen so far
2.2. the value of the better place to start or the running sum, **whichever is greater**

The max of the two would give us the solution.

#### Why does 2.2 make sense?

Consider example 2:

+3  -1    -1   -1    -1   +2    -1    +5

3  3vs2  3vs1  3vs0 3vs-1 3vs2 3vs1  3vs6
                            
                    Note: 3vs2 

By the time we get to +2:
- The value of "the better place to start" is +2.
- The value of the running sum is 1

Because we are looking for the contiguous subarray with the biggest sum, keeping what we've seen in the past doesn't make sense because it can't be better than starting with the current value.

Another way to look at it is to consider two numbers, let's say 1 and 2. If we keep adding the same numbers to 1 as the same numbers to 2, the sum starting with 2 will always be greater than 1.

So really at each step, the cumulative sum since the last "best place to start" is either the value at the current position or value at the current position *plus* the cumulative sum up to that point.

### Conclusion

At this point, we realize that what we thought about 2.2 is slightly incorrect. Rather than the running sum for everything we've seen, it's really the running sum from the best place to start we've seen so far.

## Putting Things Together

We can find the sum of the largest contiguous subarray by iterating through the list. At each step we want to keep track of two things:

1. the sum of the largest contiguous subarray we’ve seen so far
2. the cumulative sum since the last "best place to start"
- This can be determined by following the line of reasoning in *Why does 2.2 make sense?*

<style>
body > .ui-infobar, body > .ui-toc, body > .ui-affix-toc {
display: none !important;
}
</style>