View profile

DS Weekly - Find the largest sum contiguous subarray


DS Weekly

November 7 · Issue #2 · View online
Learning data-structures and algorithms need commitment. I'm gonna make it easier by sending you a solved programming challenge weekly from a curated collection of data-structures, algorithms, competitive programming questions, interview questions straight to your mailbox.

Problem Statement
Consider an array of size n. Find the subarray which has the largest sum.
Sample Input:
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). 
Optimised solution:
We are iterating through the array and for each element, we are updating two variables.
  1. Max_sum_found_so_far
  2. Max_sum_ending
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.

Solution implemented in Java
Solution implemented in Java
Here’s the link to the source code

If you got any feedback or anything you can reply to this email. 
Thank you for reading this issue. :) :) 
If you think this is helpful don’t mind to share it :) :)
Did you enjoy this issue?
If you don't want these updates anymore, please unsubscribe here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Powered by Revue