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.
If
all the numbers were positive, then the whole array is the answer.
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(n3)
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.
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.
#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:
Note: The above is
known as Kadane's Algorithm
after its founder Jay Kadane
Got a thought to share or found a bug in the code? We'd love to hear from you: