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?
Iterate from left to right and store the max possible sum if you include that particular integer.
Thanks, but I don’t think that applies here.
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.
But the same method fails here, because of the ‘mod’ value or absolute value.
Knowing the ‘max possible sum if you include an integer’ is of no use.
Example:
100, 20,-30,10
If you go with max possible sum until the 3rd element, then that is 100+20-30=90.
But the optimum would be 20-30+10=0, which is not related to the previous element.
It turns out it’s not even DP!