53. Maximum Subarray 🚀

The Question

For this article we will be covering Leetcode's '53. Maximum Subarray' question. This question is a classic problem. It's a 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.

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 technique. If you're using the Greedy Algorithm technique, then this question is considered a Easy.

We're going to be using Kadane's Algorithm, a Dynamic Programming and Greedy Algorithm. 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
2. Dynamic Programming
3. Greedy Algorithm
4. Kadane's Algorithm
5. 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 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 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& 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;

};
`

Comments

[George Withaj]

Awesome...thanks for sharing!