What happens when when two sub-sequences generate same sum?? Should we take the longer one or the shorter one? Marking the number red would only give the most recent solution(subsequence).
Contiguous means you can't skip anything in the sequence. You have a starting index and an ending index and take the sum of all the values within that subsequence.
S(0) = -6, S(1) = either -6 + 2 or 2, we will take 2. S(2) = either 2 - 4, or -4. We will take 2-4 = -2. But now you take the maximum number from this array, so the final answer is 2.
His algorithm is right and yourself are wrong. the solution array would be: [-1,-2] But now you take the maximum number from this array, which is -1. Remember, S[i] is the largest contiguous sum you can get ENDING AT (NOT UP TO) index i. Therefore you cannot simply take the last element in the solution array.
beautifully explained!!! saved a lot of time of mine..
I want you to know that, among all the explanations on youtube, your's is the best one.
By far the best explanation of the cost function out of all the videos I've seen on youtube
too bad its wrong. [-1,-2] is the counter example.
@@jackkalman8195 lol noob he said if its all negative just take the largest value (-1) in the list
Extremely helpful, thank you so much
awesome explanation, keep it up, thank you 👍👍🙂🙂
What happens when when two sub-sequences generate same sum??
Should we take the longer one or the shorter one? Marking the number red would only give the most recent solution(subsequence).
Thank you. Very good explanation.
Do you have any which teaches how to come up with a formula to solve DP ?
A[i] could be a negative number, in taht case, S[i] = S[i-1];
I think the problem you are solving is Maximum contiguous sub-array but not Maximum Contiguous Subsequence
please upload travelling salesman problem,Bellman Ford algorithm.
is this subsequence or subarray ? if its subsequence then answer should be 2 + 3 + 5 = 10. correct me if am wrong .
Contiguous means you can't skip anything in the sequence. You have a starting index and an ending index and take the sum of all the values within that subsequence.
how would you define s? the code in c++ that is
Do you have the pseudocode?
great :) thank!
For A = [-6, 2, -4]
S(2) = -2 or 2 ?
his algorithm is wrong lol.. idk why so many ppl thumbed up
S(0) = -6, S(1) = either -6 + 2 or 2, we will take 2. S(2) = either 2 - 4, or -4. We will take 2-4 = -2.
But now you take the maximum number from this array, so the final answer is 2.
His algorithm is correct, you take the maximum in the array afterwards.
@@jackkalman8195 it works perfect for me.
Bro what about this input [-1,-2]? your algorithm returned -2 and obviously the answer should be -1 lol
His algorithm is right and yourself are wrong.
the solution array would be:
[-1,-2]
But now you take the maximum number from this array, which is -1.
Remember, S[i] is the largest contiguous sum you can get ENDING AT (NOT UP TO) index i. Therefore you cannot simply take the last element in the solution array.