Dynamic Programming Optimal "Non-Decreasing Sequence"

user_8402459 0
Viewed 205

The question says,

Given an array A with N integer numbers, output the minimum number of operations needed to make the sequence non decreasing.

An operation represents choosing a number in the array A[i], summing it to A[i + 1] or A[i - 1], and deleting A[i]

The link to the problem ( spanish ): https://omegaup.com/arena/problem/Torres#problems

Example:

3
5 2 1

Answer: 2

In this case we must join all the numbers, to turn the sequence to { 8 }, which is non-deceasing

Limits:

N <= 5000
A[i] <= 10^5

I think this problem can be solved using DP, but i can't discover a state that can represent the problem in a small and correct way.

Thanks in advance.

dynamic-programming arrays algorithm
1 Answers

EDIT: I was wrong.. The following algorithm doesn't solve the problem.

It can be done in one linear scan from left to right. Let me explain my reasoning:

If you join two numbers A[i] and A[i+1], the result is greater than A[i]. If the part left of A[i] is already non-decreasing, this operation is necessary if A[i] < A[i-1].

Unnecessarily joining A[i] and A[i+1] consumes an operation and makes things more difficult right of the join, so we do it only if necessary.

  • If A[i] < A[i-1], join A[i] and A[i+1] until A[i] >= A[i-1].
  • If A[i] >= A[i-1], increment i.

P.S. The original problem description states that A[i] is in the range 1...10^5, thus explicitly excluding negative numbers, which is important for the algorithm.

user_82072280
Related