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
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.
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.
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
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.
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
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.
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
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
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.
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].
Explained simply well. great work dude. You are helping many to understand coding better.
dont you think you are missing out a lot of corner cases ??
helpful video, thanks 👍👍🙂🙂
We want this type of explanation for all DSA problems
We want this type of explanation for all DSA problems....
Great tutorial! You are doing great service to the community.
Thanks, Chiranjev! :)
@@GeeksforGeeksVideos hello bro, Can you turn on subtitles for your videos?
Very helpful and clearly explained with the concept of Dynamic Programming.
Well explained. Thanks.
noone can explain better than this. Thanks a lot !
This Explanation is enough beginners....
Super Explanation SIR !!!!
best explanation
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! :)
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.
thank you. Please post the video using Divide and Conquer for the same.
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.
Very helpful for my Algorithms class. Thank you.
You're welcome! :)
is it possible to find the least distance between all characters of a longest common subsequence ?
very nice explanation, thankyou.
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
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
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.
Is there an efficient solution to find the start and end index of the maximum contiguous subaaray?
This was really helpful, thanks !!
Thank you
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
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 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
This code dosen't work if occurance of negative number is greater than positive number.
BEST Tutorial can you please explain the problem, Angry children, 2 of hacker rank, please it is challenging
thank you sir
It's not working if all the elements of the array are negative
You can omit using variable "max_so_far" as you can return "curr_max"
How this is related to Dynamic programming?
Because you are remembering what was the maximum so far!
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
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.
if array value is only -1 then you get error in this code
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
thank you!
the example using dynamic programming is not just for contiguous subarray but all possible subarrays right?
thankyou so much
You are literally only reading out what is written over there in the website
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)"
Hey Admin do you have java tutorials for the beginners? If so please send me the link address
This algorithm fails when array is [-1]
Awesome !
Thanks!
If it is the input is only -1 it won’t work
very nice
Thanks, Nsaruna! :)
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
many will be overwhelming if you explain in hindi also
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.
3哥的口音好难懂。。
@We Can www.google.com/search?q=chinese+to+english&oq=chines+to+&aqs=chrome.1.69i57j0l4j69i60l3.2219j0j9&sourceid=chrome&ie=UTF-8
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