# Leetcode - 53, 152: Maximum Subarray Problems

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

EASY
–––

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.md
``````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 0th 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

maxSumSubarray.py
``````def maxSum(numbers):

maxSum = numbers
currentSum = numbers

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.md
``````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... ⌨️

maxProductSubarray.py
``````def maxProduct(numbers):

previousMin = numbers
previousMax = numbers
maxProduct = numbers

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

Built with ❤️ using

I am available on

Sitemap