×

# Substring with least mod value - DP?

 0 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? asked 04 Jan '15, 19:14 13●1●3 accept rate: 0% Iterate from left to right and store the max possible sum if you include that particular integer. (04 Jan '15, 23:33)

 0 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. answered 05 Jan '15, 18:53 13●1●3 accept rate: 0%
 0 answered 05 Jan '15, 18:58 13●1●3 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×939
×156
×109
×38
×3
×2
×2
×2

question asked: 04 Jan '15, 19:14

question was seen: 791 times

last updated: 05 Jan '15, 18:58