0
$\begingroup$

$T = \{t_1,t_2,\dots,t_n\} $. while $t_1,\dots,t_n \in \mathbb N$ with $t_i < t_j$ for $i < j$.

For each $t_1,\dots,t_n$, there is another value - Price. for example, for $t_1$, the price is 200.

Let $M$ be a natural number.

I have to find an Iterative algorithm which fullfil: $t_{j+1}-t_j\leq M$ for each j, and the sum of the prices in this group is MAX.

The problem is to find algorithm in $O(n)$. I think to use recursion formula for each $j$, by finding the MAX $t_i$ which fulfills $t_i+m, but it requires $O(n(\log(n))$.

Any idea please? Thank u!

  • 0
    I know. The problem is not with DP. I found DP algorithm with O(n(log(n)). I have difficult to find it in O(n).2011-03-25

1 Answers 1

1

You can find for each $i$ the maximal $j$ such that $t_j \leq t_i + M$ in linear time by using a two-pointer approach.