Consider an array of size n. Find the subarray which has the largest sum.
arr = [-2, -3, 4, -1, -2, 1, 5, -3]
Sum is 7. [4, -1, -2, 1, 5]
Sample Input - 2:
arr = [1, 12, -5, -6, 50, 3, -30, 25]
Sum is 55. [1, 12, -5, -6, 50, 3]
This problem can be solved easily using brute-force method. We iterate through each element of an array and start summing up with the following elements in the array till the end. And then return the largest sum. Simple :)
But the above solution is not the optimised way of solving the problem. The optimised way would be solving this in O(n).
We are iterating through the array and for each element, we are updating two variables.
The first variable is calculated by summing with the current element of an array. If the newly calculated value is lesser than the current element we are updating the variable Max_sum_found_so_far with the current element.
The second variable stores the maximum sum of the array at any given time. It is updated with the maximum of Max_sum_found_so_far variable found so far.
Then we return the Max_sum_ending variable.