Posts

Showing posts from November, 2017

Guide to Solving Maximal Subarray Problem using Kadane's Algorithm

Image
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.
Here are few examples to help you understand the MSP better:
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 …