# Iterative algorithm with O(n)

$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<t_j$, but it requires $O(n(\log(n))$.

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.