Given is a sequence a1, a2, . . . , an of numbers. We say that its subsequence aj1 , aj2 , . . . , ajk
Given is a sequence a1, a2, . . . , an of numbers. We say that its subsequence aj1
, aj2
, . . . , ajk
,
where 1 ≤ j1 < j2 < . . . < jk ≤ n, is kind-of-increasing, if for every three consecutive
elements in this subsequence, the average of the first two elements is smaller than the third
element. Formally, (aji+aji+1 )/2 < aji+2 holds for every i ∈ {1, 2, . . . , k−2}. Design an O(n
3
)
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
I'm not sure if the question is understood here, but this problem utilizes a 2D array as OPT. OPT[i, j] = is the largest kind of increasing subsequence we can obtain ending at
by Bartleby Expert
