## Posts

Showing posts from November, 2017

### Guide to Solving Maximal Subarray Problem using Kadane's Algorithm

What is 'Maximal Subarray Problem'(MSP)?

Given an array having both positive and negative numbers, we need to find a continuous part of the array whose elements when added gives the largest possible sum.
1. consider the array [-1, 2, -1, 3]
Now, here is a list of all the possible subarrays along with the sum of their elements:

ELEMENTSSUMstart indexend index-1-100-1, 2101-1, 2,-1002-1, 2,-1, 330322112,-11122,-1, 3413-1-122-1, 32233333
From, the above table, its obvious that the answer is [ 2,-1, 3].
All other subarrays sum up to a value that is less than 4.

2. consider the array [-1,-2]

Here, the answer would be [-1]

3. consider the array [ 1, 2, 3]

Here the answer would be [ 1, 2, 3]

I hope you got the idea of what is 'Maximal Subarray Problem' by now.

Given an array, how can we find the MSP?

One way to find the MSP for a given array is to check out all the possible subarrays and thus find …