# Leetcode - 53, 152: Maximum Subarray Problems

## Given a list of numbers we need to find a subarray which generates maximum sum or product

The maximum subarray problems are one of the easiest to solve but sometimes a small mistake can make it very tough and there can be a cascading effect to the whole solution, so it's better to practice every small and trivial problem out there.

## What's the question?

Given an integer array `nums`

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

### Let's look at an example

```
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Subarray: [4, -1, 2, 1]
```

For this problem we will start with two variables the maxium sum or `maxSum`

with value of the 0^{th} index in list. And the sum at current index in the iteration i.e. `currentSum`

which will be same as the `maxSum`

while initializing them
Then we will iterate over the the remaining list and check if the number at that index is larger than the `currentSum + number`

and if it is we will update the `currentSum`

.
But this doesn't mean that the max sum should also be updates we will check the maximum of `currentSum`

and `maxSum`

and update the `maxSum`

based on that result.

## Jump into code

```
def maxSum(numbers):
maxSum = numbers[0]
currentSum = numbers[0]
for ix, number in enumerate(numbers[1:]):
currentSum = max(number, currentSum + number)
maxSum = max(currentSum, maxSum)
return maxSum
```

Now let's check one more type of **Max Subarray** question the **Maximum Product Subarray**.

## Again, what's the question?

Given an integer array `nums`

, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

### Let's look at an example

```
Input: nums = [2,3,-2,4]
Output: 6
Subarray: [2, 3]
```

### How's this different than the Max Sum Subarray problem?

In multiplication we need to check of negatives also two negatives become a positive i.e. we can get a bigger positive number by taking the product of two bigger negative numbers and when that number is multiplied with a positive number the output will be more larger.

We tackle this by keeping track of the minimum number in the list as well. So let's get into the coding... ⌨️

```
def maxProduct(numbers):
previousMin = numbers[0]
previousMax = numbers[0]
maxProduct = numbers[0]
for ix, number in enumerate(numbers[1:]):
currentMin = min(previousMax * number, previousMin * number, number)
currentMax = max(previousMax * number, previousMin * number, number)
maxProduct = max(maxProduct, currentMax, currentMin)
previousMin = currentMin
previousMax = currentMax
return maxProduct
```

And we are done with this 😅

That's it for this blog, hope you found this helpful. You can connect with me on Twitter