You are not logged in. Please login at to post your questions!


Substring with least mod value - DP?

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

vikramnitin9's gravatar image

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) Organic-Shilling0★

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

vikramnitin9's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 04 Jan '15, 19:14

question was seen: 800 times

last updated: 05 Jan '15, 18:58