Maximum Contiguous Subsequence - Dynamic Programming

[@JayPatel12928]

I want you to know that, among all the explanations on youtube, your's is the best one.

[@fitoor0997]

beautifully explained!!! saved a lot of time of mine..

[@neobonzi]

By far the best explanation of the cost function out of all the videos I've seen on youtube

[@jackkalman8195]

too bad its wrong. [-1,-2] is the counter example.

[@AjayByadgi]

@@jackkalman8195 lol noob he said if its all negative just take the largest value (-1) in the list

[@sbonelo]

Extremely helpful, thank you so much

[@SmartProgramming]

awesome explanation, keep it up, thank you 👍👍🙂🙂

[@KrishanuKonar]

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).

[@sabio234]

Do you have any which teaches how to come up with a formula to solve DP ?

[@ffatheranderson]

Thank you. Very good explanation.

[@eithanmartinez2852]

Do you have the pseudocode?

[@PreethaDatta]

how would you define s? the code in c++ that is

[@technomissilecraft4532]

please upload travelling salesman problem,Bellman Ford algorithm.

[@thanga2317]

is this subsequence or subarray ? if its subsequence then answer should be 2 + 3 + 5 = 10. correct me if am wrong .

[@RooonilWazlib]

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.

[@groupsvkg]

For A = [-6, 2, -4] S(2) = -2 or 2 ?

[@jackkalman8195]

his algorithm is wrong lol.. idk why so many ppl thumbed up

[@oliverliu9205]

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.

[@matheusrotta1589]

His algorithm is correct, you take the maximum in the array afterwards.

[@ffatheranderson]

@@jackkalman8195 it works perfect for me.

[@kameshsriram]

I think the problem you are solving is Maximum contiguous sub-array but not Maximum Contiguous Subsequence

[@jasdn93bsad992]

A[i] could be a negative number, in taht case, S[i] = S[i-1];

[@chuongxl]

great :) thank!

[@jackkalman8195]

Bro what about this input [-1,-2]? your algorithm returned -2 and obviously the answer should be -1 lol

[@oliverliu9205]

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.