You were wrong in stating that S(i) represents the maximum sum till ith index. It should be stated as the maximum contiguous sum of the window that has a(i) as its endpoint. Meaning thereby that S(i) does not represent the maximum contiguous sum of the array from 1 to i. It is the maximum sum of the window that terminates at a(i) only and cannot terminate at any index < i.
Great video thanks! @joel, s(i) = the maximum sum of a sequence that ends with the ith element so for s(2) it must include the -3. S(i) isn't the maximum subsequece in the array from 0 to i. I thought that at first too. That is why at the end you have to select the max s(i) value rather than simply s(n)
Hi Atul, as we have S[i] for all i from 1 to 8 then it becomes very simple to find the window. Here S[7] is maximum, now work backwards from S[7] and check if S[7] = S[6] + A[7] if yes then window contains A[6..7] Then check if S[6] = S[5] + A[6] if yes include this keep on going till this becomes false. This way you will get the starting point too.
saurabh, appreciate the effort in making the video. I feel it is important to stress that s(i) is the maximum sum contiguous subsequence between [1, i] "ending exactly at i" otherwise i was confused for a short moment. If you dont mention that, then in your example s(2) = -2.
Hi Saurabh, Excellent videos. Learnt a lot. Just a simple question . What is the condition when you are extending the window and how you are initializing the window
sorry, my mistake in getting this. S[I] means it should end at I and hence s[i] = Max { s(i-1) + A[i] , A[i] } mentioned by Saurabh is correct. In the end he actually takes makes of all S[I]. Only one small suggestion Saurabh. While u were drawng the I and showing the window if u include the I in the window, it becomes slightly moe evident that S[I] means window need to end at I. Thx again for the informative and nicely done video.
Unfortunately Saurabh, you are wrong. You made a huge mistake in the definition of S(i). Below is the correct definition: S(i) = max{s(j < i) + A(i), A(i)} j is all the positions that are to the left of i. Find the max of whichever one of that, then add the element at current index. If that is greater than element i itself, which of course means that element i is positive, then that is the greatest subset from index 0 to that i. Just something to clarify and hope you understand.
Yes Mr. Feng is correct. Here is the small program for it. public static void main(String[] args) { int sum = 0; int largest = array[0]; for (int i = 0; i < array.length; i++) { sum = sum + array[i]; if(sum < 0) { largest = max(largest, sum, array[i]); sum = 0; continue; } largest = max(largest, sum, array[i]); } System.out.println(largest); } // Here max function gives the max of three integer numbers. Please let me know if it fails for some array input.
In that case, if u input an array which has the max contiguous sum containing a sub-array that includes some negative numbers, ur algo would totally neglect tht presence of those negative numbers in the total sum of the max contiguous sub-array....eg: for the array used in example of this video, the sum would be 10 instead of 7, which is the correct andwer...it would neglect -1,-2 between 4 and 1.
Hi, Thanks for the video..I have a confusion.. How can we keep the track of the window? For ex S[7] gives the maximum sum but it doesn't tell the starting point.
yes at S(2) should be -2 rather than -3. The issue in Saurabh's program looks like s[i] = Max { s(i-1) , s(i-1) + A[i] , A[i] } rather than s[i] = Max { s(i-1) + A[i] , A[i] } as pointed by Saoud Al-Roomi too. Otherwise video is good to understand the concept.
Thanks for all your videos. This program can be done without dynamic programming in O(n) time complexity. Please find the code below: public static int maxSubsequenceSum(int[] arr) { int maxSubSum = arr[0]; int currentSum = 0; for (int i=0; i < arr.length; i++) { if (currentSum < 0 && currentSum < arr[i]) { currentSum = arr[i]; } else { currentSum += arr[i]; } if (currentSum > maxSubSum) { maxSubSum = currentSum; } } return maxSubSum; }
Exactly. He is wrong. It's clearly why. The definition of S(i) he gave starts to become wrong in his example. How is S(2) equal to -3? It doesn't even make any sense. He's not including S(1) which is -2 which would clearly make S(2) also -2. But he has it as -3 which is beyond me. I thought he was a Professor. lol. he should know better.
The definition of s(i) is not correct. here is the correct one: trace = [] for i=1 ... n: o'(i) = max{o'(i-1) + a[i], 0} # we keep 0 or positives. o(i) = max{o'(i), o(i-1)} if o'(i) > o(i-1): trace.append('sequence') else: trace.append('jump') starting from trace[-1] go reverse to reach to the first 'sequence' at j. All o'(j) until j=0 is part of the solution if o'(j) > 0.
You were wrong in stating that S(i) represents the maximum sum till ith index. It should be stated as the maximum contiguous sum of the window that has a(i) as its endpoint. Meaning thereby that S(i) does not represent the maximum contiguous sum of the array from 1 to i. It is the maximum sum of the window that terminates at a(i) only and cannot terminate at any index < i.
+Joseph Ralph Yea i think u r right, if S(i) were to represent the maximum sum till ith index, then S(4) will be 4 instead of 3.
+Joseph Ralph yes you are right. +saurabhschool please revise this video
Great video thanks! @joel, s(i) = the maximum sum of a sequence that ends with the ith element so for s(2) it must include the -3. S(i) isn't the maximum subsequece in the array from 0 to i. I thought that at first too. That is why at the end you have to select the max s(i) value rather than simply s(n)
Hi Atul, as we have S[i] for all i from 1 to 8 then it becomes very simple to find the window. Here S[7] is maximum, now work backwards from S[7] and check if S[7] = S[6] + A[7] if yes then window contains A[6..7] Then check if S[6] = S[5] + A[6] if yes include this keep on going till this becomes false. This way you will get the starting point too.
saurabh, appreciate the effort in making the video. I feel it is important to stress that s(i) is the maximum sum contiguous subsequence between [1, i] "ending exactly at i" otherwise i was confused for a short moment. If you dont mention that, then in your example s(2) = -2.
Hi Saurabh, Excellent videos. Learnt a lot. Just a simple question . What is the condition when you are extending the window and how you are initializing the window
sorry, my mistake in getting this. S[I] means it should end at I and hence s[i] = Max { s(i-1) + A[i] , A[i] } mentioned by Saurabh is correct. In the end he actually takes makes of all S[I].
Only one small suggestion Saurabh. While u were drawng the I and showing the window if u include the I in the window, it becomes slightly moe evident that S[I] means window need to end at I.
Thx again for the informative and nicely done video.
Unfortunately Saurabh, you are wrong. You made a huge mistake in the definition of S(i). Below is the correct definition:
S(i) = max{s(j < i) + A(i), A(i)}
j is all the positions that are to the left of i. Find the max of whichever one of that, then add the element at current index. If that is greater than element i itself, which of course means that element i is positive, then that is the greatest subset from index 0 to that i.
Just something to clarify and hope you understand.
I think he means to solve longest contiguous subsequence with max sum.
Yes Mr. Feng is correct. Here is the small program for it.
public static void main(String[] args) {
int sum = 0;
int largest = array[0];
for (int i = 0; i < array.length; i++) {
sum = sum + array[i];
if(sum < 0) {
largest = max(largest, sum, array[i]);
sum = 0;
continue;
}
largest = max(largest, sum, array[i]);
}
System.out.println(largest);
}
// Here max function gives the max of three integer numbers.
Please let me know if it fails for some array input.
Thanks a lot, your videos are very useful to understand the concept.
In that case, if u input an array which has the max contiguous sum containing a sub-array that includes some negative numbers, ur algo would totally neglect tht presence of those negative numbers in the total sum of the max contiguous sub-array....eg: for the array used in example of this video, the sum would be 10 instead of 7, which is the correct andwer...it would neglect -1,-2 between 4 and 1.
Hi, Thanks for the video..I have a confusion.. How can we keep the track of the window? For ex S[7] gives the maximum sum but it doesn't tell the starting point.
thanks ur all videos are very helpfull and simple. n understandable..
Nice video, but you may have also explained how this algorithm follows optimal substructure and overlapping subproblems..
Thanks Fatemeh, I am happy that you liked my videos
Thank you so much, I had a hard time understanding dynamic programming before this video.
yes at S(2) should be -2 rather than -3. The issue in Saurabh's program looks like s[i] = Max { s(i-1) , s(i-1) + A[i] , A[i] } rather than s[i] = Max { s(i-1) + A[i] , A[i] } as pointed by Saoud Al-Roomi too.
Otherwise video is good to understand the concept.
what if the subsequence was not continuos...how would it had worked?
At S(2), you say the max sub sequence is {-3}, but isn't the max sub sequence simply {-2} ?
Thanks for all your videos. This program can be done without dynamic programming in O(n) time complexity. Please find the code below:
public static int maxSubsequenceSum(int[] arr) {
int maxSubSum = arr[0];
int currentSum = 0;
for (int i=0; i < arr.length; i++) {
if (currentSum < 0 && currentSum < arr[i]) {
currentSum = arr[i];
} else {
currentSum += arr[i];
}
if (currentSum > maxSubSum) {
maxSubSum = currentSum;
}
}
return maxSubSum;
}
thanks for your explanation it helped me a lot i wish you would have done it in java or something :)
There seems something wrong with the last element.
The definition of S(i) is max subsequence till the ith element. How can it be less than i-1.
Exactly. He is wrong. It's clearly why. The definition of S(i) he gave starts to become wrong in his example. How is S(2) equal to -3? It doesn't even make any sense. He's not including S(1) which is -2 which would clearly make S(2) also -2. But he has it as -3 which is beyond me. I thought he was a Professor. lol. he should know better.
Mistakes happen...but he is good with other videos..watched only his videos and cracked so many interviews...wanna say thanks!!!
Videos are very good but background noise is too much... could you please do some audio edit to remove noise !!!
Thank you! really clear explanation.
it's just that the title is missing the word contiguous (or Kadane's algorithm to be precise)
@Joel Berghoff -- Yes I think the definition of S[i] is vague and doesn't fully explain what the mathematical relation states
Thanks, that was very helpful.
maximum contiguous sub sequence sum should be 6 got by adding 1 and 5....explain!!!
nice article, very clear :) thx a lot
you are welcome sumit :)
Good explanation!
Great lecture :)...You were using a desktop I presume. I heard your UPS go teeeeeet...:P
Shouldn't it be s[i] = Max { s(i-1) , s(i-1) + A[i] , A[i] }
Because if the array is 1 2 3 -5 yours will not work as i understand
This is not the right algo : It will give the result = 24 instead of 25 {2,3,-1,10, 11}
{-1,2,3,-1,10,11,-10,0,4,5}
Gotcha.. Thanks again :)
welcome
I liked it... Thanks :)
wow.thanks sir
you are welcome Camera
Good explanation but poor demonstration. You didn't at all explain the approach you used to find the recursive function and what about the base case?
The definition of s(i) is not correct. here is the correct one:
trace = []
for i=1 ... n:
o'(i) = max{o'(i-1) + a[i], 0} # we keep 0 or positives.
o(i) = max{o'(i), o(i-1)}
if o'(i) > o(i-1):
trace.append('sequence')
else:
trace.append('jump')
starting from trace[-1] go reverse to reach to the first 'sequence' at j. All o'(j) until j=0 is part of the solution if o'(j) > 0.
rather take kadane algo..n put this down! Just trying to help you, i like ur other videos!
Thanks but for me you skipped to many steps. I like this pace Programming Interview: Dynamic Programming: Coin Change Problem
Thanks for your comment, I will take care of the pace and see how coin change problem has been explained by me
Hello ,I found a 74% OFF coupon to Learn Matlab Udemy course
Couponcode: 2016ML25
www.udemy.com/learn-matlab/?couponCode=2016ML25
ADAMIM BENİM
wasted my time ..