Largest Sum Contiguous Subarray | GeeksforGeeks
Vložit
- čas přidán 31. 10. 2016
- Find complete code at GeeksforGeeks article: www.geeksforgeeks.org/largest-...
Practice Problem Online Judge: practice.geeksforgeeks.org/pro...
This video is contributed by Harshit Jain.
dont you think you are missing out a lot of corner cases ??
An optimization for the case where all numbers are negative,it would be to check at the end of for loop if the max_so_far is 0 and only if it is 0 you make another for loop and find the maximum negative element.
Since in real scenarios it does not happen too often to have all numbers negative,the above approach is better
You don't have to loop again. You can just initialize the variables to the first element of the array. i.e max_so_far = max_ending_here = A[0].
We want this type of explanation for all DSA problems
Explained simply well. great work dude. You are helping many to understand coding better.
helpful video, thanks 👍👍🙂🙂
Hey Admin do you have java tutorials for the beginners? If so please send me the link address
Very helpful and clearly explained with the concept of Dynamic Programming.
If I want to keep track of the starting and ending positions of the maximum sum subarray using the dp solution, how should I go about with it?
every time you reset the value to 0 for max_ending_here keep that index + 1 value saved, assume, start_index.
every time you update max_so_far save with it [start_index, current value of iterator]
then you splice it and print it.
noone can explain better than this. Thanks a lot !
Great tutorial! You are doing great service to the community.
Thanks, Chiranjev! :)
@@GeeksforGeeksVideos hello bro, Can you turn on subtitles for your videos?
Is there an efficient solution to find the start and end index of the maximum contiguous subaaray?
This Explanation is enough beginners....
This was really helpful, thanks !!
thank you. Please post the video using Divide and Conquer for the same.
We want this type of explanation for all DSA problems....
Thank you, will try to implement it later on CPP
Great!
Here's a practice problem for this: practice.geeksforgeeks.org/problems/kadanes-algorithm/0
Thank you so much @GeeksforGeeks, I couldn't find any better explanation than this !!
You're welcome, Amith! :)
Well explained. Thanks.
is it possible to find the least distance between all characters of a longest common subsequence ?
Can we have one code for the positive, positive & negative and all negative numbers?
Looks like this algo is returning sum of max possible sub array , but not actually the subarray, As per the title and the question algo should return the contiguous subarray
very nice explanation, thankyou.
Super Explanation SIR !!!!
Very helpful for my Algorithms class. Thank you.
You're welcome! :)
the example using dynamic programming is not just for contiguous subarray but all possible subarrays right?
best explanation
thank you!
We could easily make this work for both positive and negative arrays by modifying max_ending_here = max (max_ending_here + a[i], a[i]) and remove the 'max_ending_here = 0' assignment.
Thank you
the algorithms fails when the array is {-2, -3, 4, -1, -12, 1, -5, 3} it finds 1 as max sum
It seems to be producing 4 as output.
Please see: ide.geeksforgeeks.org/yjoLoCMS5R
How this is related to Dynamic programming?
Because you are remembering what was the maximum so far!
It will fail for arrays having all negative values. e.g. [-1,-2,-3].
how?
still the max value will be -1 so it is correct
public int maxSubArray(final List A)
{
int end =0,far=0,counter=0;
for(int i=0;i
This code dosen't work if occurance of negative number is greater than positive number.
thank you sir
thankyou so much
this video explain about working of algorithm with an example which is very good but can anybody tell me how to reach to this algorithm by yourself if no such algorithm exists like I want to know how to think of this solution.
BEST Tutorial can you please explain the problem, Angry children, 2 of hacker rank, please it is challenging
Awesome !
Thanks!
what if all elements are negative, then this would fail!
thats the idea, who the hell you want to find the largest sum in negative array
Tal K I want to find. and this could be a use case in gaming etc..
this works only if not all are negative. If all are negative, you just pick the greatest number in the sequence.
so, first i will traverse in array to know if all are negative, and then i will againcheck for greates element. 2n solution you are saying?
Anubhava Gupta yes. First check if all are negative, if yes, return the greatest. If not, do the algorithm
if array value is only -1 then you get error in this code
This algorithm fails when array is [-1]
It's not working if all the elements of the array are negative
For the input [1,2,-3,4,5,-6,7,8] it's returning 18, whereas the answer should be 7+8 = 15
18 is correct. The subarray would be 4+5+(-6)+7+8 =18
[4,5,-6,7,8] = 18 > [7,8] = 15
You can omit using variable "max_so_far" as you can return "curr_max"
Don't you think this algorithm is missing the scenario where all numbers will be negative.
Sorry didn't see the second part that will solve the all negative case
You are literally only reading out what is written over there in the website
if all the elements are negative then just return the maximum value of the array
so use a flag to check if the input array has at least one positive element
can anybody tell me how will we print largest contiguous sum array that is in this case 4,-1,-2,1,5 .!! #GeeksforGeeks
Hi Sumish, have a look at my post. It also finds out the starting and ending indices of Maximal subarray using the Kadane's algorithm: www.thecodenote.com/2017/11/guide-to-solving-maximal-subarray.html
max_so_far =4, max_ending_here=4,max_ending_here=3,max_ending_here=1,max_ending_here=2,max_ending_here=7, max_so_far=7...done!! you take all the elements in the array and get the maxsum. +sumish ajmani
very nice
Thanks, Nsaruna! :)
if the array is [-1] or [-1, -2]
it will return 0;
it should return -1 . , -2 respectively
int Solution::maxSubArray(const vector &A)
{
int max_so_far=INT_MIN,max_ending_here=0;
int size=A.size();
for(int i=0;imax_so_far)
max_so_far=max_ending_here;
if(max_ending_here
add "while max(arr) < 0; return max(arr)"
many will be overwhelming if you explain in hindi also
If it is the input is only -1 it won’t work
I don't find this kind of explanation useful where you straightaway start proving your pseudocode right instead of explaining the intuition behind it. mycodeschool is better in terms of it.
dude we need it to find the max subsequence sum.. he is explaining how to do it. you are here because you want to understand how do code works.. not why we need it since why we need it is for what ever rzn you are here.
exactly. anyone with basic skills can explain the pseudocode.
3哥的口音好难懂。。
@We Can www.google.com/search?q=chinese+to+english&oq=chines+to+&aqs=chrome.1.69i57j0l4j69i60l3.2219j0j9&sourceid=chrome&ie=UTF-8
You NEED to explain the intuition/approach behind the problem NOT THE PSEUDO CODE. Anyone can understand code, but not the approach. This is just lazy work with no creativity.
We want this type of explanation for all DSA problems
We want this type of explanation for all DSA problems
We want this type of explanation for all DSA problems
We want this type of explanation for all DSA problems
We want this type of explanation for all DSA problems
We want this type of explanation for all DSA problems
We want this type of explanation for all DSA problems