Largest Sum Contiguous Subarray

Given an unordered integer array, find the contiguous subarray which has the largest sum.

Solution: To attempt this question, we need to make some observations first.

1. If all the numbers were positive, then the whole array is the answer.

2. If we try to find maximum sum among all possible contiguous subarrays, then the possible subarrays would be N subarrays of size 1, N-1 subarrays of size 2, N-2 subarrays of size 3 and so on.

So total number of subarrays would be N + N-1 + N-2 ... 1 = N(N+1)/2

To find sum of each subarray, we would need to add elements of each array.

So, brute force solution is O(n³)

3. If all numbers were negative, then there is no point in trying to find the subsequence because addition of numbers in any subarray would be lesser than the constituent elements. Hence, in such a case, largest number in the array is the subarray we are seeking as answer.

4. If we encounter a negative number while summing a subarray and the negative number’s magnitude is lesser than the current sum, then we can continue addition because the positive sum would still contribute to positiveness of the subarray. If the negative number’s magnitude is greater than the current sum, then the current subarray has to end there only.

5. #4 holds the entire logic of the algorithm. When current sum goes below 0, it becomes equivalent to a “first-negative” number in the array which must be ignored for further computation. Also, since the addition of the current number has made the sum below 0, there is no point in considering sum from any index till current index for further computation because it will only be more negative.

With the above points, the logic for this can be as follows: