Answers to: Substring with least mod value - DP?https://inoi15.discuss.codechef.com/questions/60742/substring-with-least-mod-value-dp<p>This is from IARCS Problem archive (DEVIOUS). Given a sequence of integers, how do you find the contiguous substring with the absolute value of the sum of its numbers being minimum?
Is it even DP? How do you relate it to smaller subproblems?</p>enMon, 05 Jan 2015 18:58:15 +0530Answer by vikramnitin9https://inoi15.discuss.codechef.com/questions/60742/substring-with-least-mod-value-dp/60802<p>It turns out it's not even DP!
<a href="http://stackoverflow.com/questions/16996221/closest-to-zero-absolute-value-sum-of-consecutive-subsequence-of-a-sequence-of">http://stackoverflow.com/questions/16996221/closest-to-zero-absolute-value-sum-of-consecutive-subsequence-of-a-sequence-of</a></p>vikramnitin9Mon, 05 Jan 2015 18:58:15 +0530https://inoi15.discuss.codechef.com/questions/60742/substring-with-least-mod-value-dp/60802Answer by vikramnitin9https://inoi15.discuss.codechef.com/questions/60742/substring-with-least-mod-value-dp/60801<p>Thanks, but I don't think that applies here.<br>
Greatest subsequence can be solved using standard DP as in the link. There, we have two cases - either we continue the sequence or we start a new one, depending on which is optimal.<br>
But the same method fails here, because of the <b>'mod' value or absolute value.</b><br>
Knowing the 'max possible sum if you include an integer' is of no use.<br>
Example:
100, 20,-30,10<br>
If you go with max possible sum until the 3rd element, then that is 100+20-30=90. <br>
But the optimum would be 20-30+10=0, which is not related to the previous element.</p>vikramnitin9Mon, 05 Jan 2015 18:53:58 +0530https://inoi15.discuss.codechef.com/questions/60742/substring-with-least-mod-value-dp/60801Comment by Organic-Shilling on vikramnitin9's questionhttps://inoi15.discuss.codechef.com/questions/60742/substring-with-least-mod-value-dp#60763<p>Iterate from left to right and store the max possible sum if you include that particular integer.</p>Organic-ShillingSun, 04 Jan 2015 23:33:44 +0530https://inoi15.discuss.codechef.com/questions/60742/substring-with-least-mod-value-dp#60763