53. Maximum Subarray 🚀
Tags: javascript, cpp, python, leetcode
Published: 2022-08-03 14:44:00



## The Question
For this article we will be covering Leetcode's '[53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)' question. This question is a classic problem. It's a [Greedy Algorithm](https://en.wikipedia.org/wiki/Greedy_algorithm) problem.

Question:

> Given an integer array nu`ms, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
> A **subarray** is a **contiguous** part of an array.

 

![Example](https://easycodebase.com/wp-content/uploads/2021/11/max-subarray-746x560.png)


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

## Explaining The Question
This Question is rated **Medium**. Which is arguable, this could be considered a **Easy** question, if you're not using the [Divide and Conquer](https://en.wikipedia.org/wiki/Divide_and_conquer) technique. If you're using the [Greedy Algorithm](https://en.wikipedia.org/wiki/Greedy_algorithm) technique, then this question is considered a **Easy**.

We're going to be using [Kadane's Algorithm](https://en.wikipedia.org/wiki/Kadane's_algorithm), a [Dynamic Programming](https://en.wikipedia.org/wiki/Dynamic_programming) and [Greedy Algorithm](https://en.wikipedia.org/wiki/Greedy_algorithm). [Kadane's Algorithm](https://en.wikipedia.org/wiki/Kadane's_algorithm) is a greedy algorithm that finds the maximum sum of a subarray. It's a very simple algorithm, and it's entirely possible to come up with this algorithm without knowing it. It's very intuitive.

***

##  Recommended Knowledge (Or what you're about to learn)
1. [Array](https://en.wikipedia.org/wiki/Array)
2. [Dynamic Programming](https://en.wikipedia.org/wiki/Dynamic_programming)
3. [Greedy Algorithm](https://en.wikipedia.org/wiki/Greedy_algorithm)
4. [Kadane's Algorithm](https://en.wikipedia.org/wiki/Kadane's_algorithm)
5. [Big O Notation](https://en.wikipedia.org/wiki/Big_O_notation)

## What do we know?
1. We have an array, that possibly has negative numbers and we need to find the maximum sum of a given sub array.

## How we're going to do it:

We're going to use [Kadane's Algorithm](https://en.wikipedia.org/wiki/Kadane's_algorithm) to find the maximum sum of a sub array. Meaning that we're going to carry the sum of the current max sub array, and if we find a number that is greater than the sum of the max sub array, restart the sub arrays value to be that of the current number, or we will keep adding the numbers to the sub array.

All the while we're always keep track on if the new max sum array is greater than the current max sum. We repeat this process for every number in the array.

1. We start with a max sum of 0. As it's possible that we have a array of 1 length, so thus it's max sum is itself.
2. We also start with a max sub array of -Infinity. This is because we want to find the maximum sub array, and we don't want to start with a sub array of 0 as their is negatives within the array.

## Big O Notation:
* Time Complexity:   *O(**n**)* | Where ***n*** is the length of the array.
* Space Complexity: *O(**1**)*  | As we never allocate any additional memory.

Can this be improved? 
Well, by the big O notation, NO! But we can use a [Divide and Conquer](https://en.wikipedia.org/wiki/Divide_and_conquer) technique to improve the speed but that'll use linear memory. 

***

# Python Solution

```

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        subArraySum = float('-inf')
        maxSubSum   = nums[0]
        
        for num in nums:
            subArraySum = max(num, subArraySum + num)
            maxSubSum   = max(maxSubSum, subArraySum)
        
        return maxSubSum;

```

# C++ Solution

```
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int subArraySum = -10000;
        int maxSubSum = nums[0];
        
        for(const auto& num : nums) {   
           subArraySum = max(num + subArraySum, num);
           maxSubSum = max(maxSubSum, subArraySum);
        }
        
        return maxSubSum;
    }
};
```

# Javascript Solution

```
var maxSubArray = function (nums) {

    let sub_array_sum = -Infinity; 
    let max_sub_sum = nums[0]; 

    for (const num of nums) {
        sub_array_sum = Math.max(num, sub_array_sum + num);
        max_sub_sum = Math.max(max_sub_sum, sub_array_sum);
    }

    return max_sub_sum;
};
```