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. 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: ELEMENTS SUM start index end index -1 -1 0 0 -1, 2 1 0 1 -1, 2,-1 0 0 2 -1, 2,-1, 3 3 0 3 2 2 1 1 2,-1 1 1 2 2,-1, 3 4 1 3 -1 -1 2 2 -1, 3 2 2 3 3 3 3 3 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....