# PROBLEM LINK:

**Editorialist:** Adithya Dsilva

# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

Binary Search (generalized version), Dynamic Programming, Longest Increasing Subsequence

# PROBLEM:

You are given an array A consisting of N integers. You are also given an integer L.

A sequence of indices (i_1,i_2,\dots,i_k) is said to be an interesting sequence of size k if

The **cost** of an interesting sequence is defined as

Find the maximum possible **cost** over all interesting sequences of size L.

# QUICK EXPLANATION:

**We start by considering the case where all elements in A are distinct.**

We maintain an array P such that

Thus, P_i refers to the index of the i^{th} largest element in array A.

Any subsequence of the set (P_1,P_2,\dots,P_N) is thus an interesting sequence. Also, if (i_1,i_2,\dots,i_k) is an interesting sequence, then it is a subsequence of array P.

For a given cost D, we try to determine if there exists a subsequence (P_{i_1},P_{i_2},\dots,P_{i_L}) of P with cost \ge D. We can determine this using DP in O(N^2). The monotonic condition over D enables us to binary search over the valid values of D to determine the maximum possible cost in O(N^2\log N).

For the case where elements are non-distinct, we determine valid values i,j such that A_{P_i}=A_{P_j} and |P_i-P_j| is maximum. We then set the lower bound of our search space to |P_i-P_j| and proceed binary searching as usual.

# EXPLANATION:

**Note :** We use 1-based indexing in the editorial.

**We start by only considering the case where all elements in A are distinct.**

We know that sequence (i_1,i_2,\dots,i_k) is an interesting sequence only if A_{i_1}>A_{i_2}>\dots>A_{i_k} (the equality sign has been removed as we are only dealing with distinct elements in array A)

We maintain an array P such that, P_i refers to the index of the i^{th} largest element in array A.

In other words,

should hold.

## How do we construct array P?

This can be achieved by making an array of pairs B, where B_i\text{.first}=A_i and B_i\text{.second}=i. We can then sort B in non-decreasing order of the first term of the pairs. Then,

which implies

Therefore, P_i=B_i\text{.second} for all valid i.

**Claim :** Any subsequence of the set (P_1,P_2,\dots,P_N) is an interesting sequence.

## Proof

As per our definition of array P,

Thus, A_{P_a}>A_{P_b} if and only if a<b.

Now, if (P_{i_1},P_{i_2},\dots,P_{i_k}) is a subsequence of the aforementioned set, then i_1<i_2<\dots<i_k must hold.

This would imply

which means this subsequence is an interesting sequence!

Note that the converse of the above claim is also true. If any sequence (i_1,i_2,\dots,i_k) is an interesting sequence, it is a subsequence of array P.

## Proof

Let (i_1,i_2,\dots,i_k) be an interesting sequence. Let j_1,j_2,\dots,j_k be values such that P_{j_x}=i_x for all valid x.

Now, as (i_1,i_2,\dots,i_k) is an interesting sequence,

holds.

In our previous claim, we proved that A_{P_a}>A_{P_b} if and only if a<b. Thus, from (1) we incur that, j_1<j_2<\dots<j_k.

Thus, sequence i_1,i_2,\dots,i_k is a subsequence of array P!

The answer to this problem is thus, the maximum possible cost, over all subsequences of array P of size L.

Can we determine for some fixed value D, if there exists an subsequence of P with cost \ge D? We could then simply find the largest value of D, such that a subsequence of size L with cost D exists.

More formally, for a particular value of D, we try to determine if there exists a subsequence (P_{i_1},P_{i_2},\dots,P_{i_L}) such that

How do we do this? This can be solved in O(N^2) by tweaking the DP solution of the Longest Increasing Subsequence problem.

**Note :** Readers are requested to acquaint themselves with the DP solution of the LIS problem, as the states of the DP shall **not** be discussed in-depth here.

Define DP_i as the longest subsequence of P with cost \ge D, where the last term of the subsequence is P_i. DP_i is defined as 1+DP_x\space(x<i), where |P_i-P_x|\ge D and DP_x is maximum possible. If there exists no valid value for x, DP_i=1, which is the base case of our DP solution.

Formally, we define

Then we check if there exists a valid i such that DP_i\ge L. If yes, it implies that it is possible to have an interesting sequence of size L with cost \ge D. Otherwise, it is impossible.

Call the above DP solution \text{Possible}(). \text{Possible}(D) returns `true`

if it is possible to have an interesting sequence of size L with cost \ge D and returns `false`

otherwise. Thus, we simply have to find the largest valid value D such that \text{Possible}(D) returns `true`

.

However, since we are checking over all possible values of D, this solution is not efficient enough to pass the last subtask! Before delving into the optimal solution, let us analyze what we have done so far.

## Analysis of above approach

Computing the values of array P can be done in O(N\log N) by sorting array A.

The DP solution takes O(N^2) time to determine the size of the largest subsequence with cost \ge D. As there are N different valid values for D (the lower and upper bounds on D are 0 and N-1 respectively), determining the maximum possible cost takes O(N^2*N)=O(N^3) time.

Thus, the overall time complexity is

which wonâ€™t pass in the last 2 subtasks!

We can greatly optimize our solution by making one vital observation.

**Claim :** If \text{Possible}(D) returns `false`

for some D, then \text{Possible}(D') also returns `false`

for all D'\ge D.

## Proof

Let us assume the contrary. Imagine \text{Possible}(D) return `false`

and assume there exists a D'\ge D such that \text{Possible}(D') returns `true`

.

\text{Possible}(D') returns `true`

means that the maximum cost possible over all subsequences of size L is \ge D'. This would imply that maximum cost possible is \ge D, since D'\ge D.

Hence, \text{Possible}(D) should actually return `true`

. Thus contradiction and we are done!

As our claim proves the monotonicity of the problem, we can efficiently reduce the search space by binary searching on the maximum possible cost (the lower and upper bounds of the search space are 0 and N-1 respectively)! A tutorial on this technique has been linked in the prerequisites above.

Coming back to the original constraints, let us handle the case where the elements in A are non-distinct. When elements are non-distinct,

and the equality condition tells us that there might exist valid integers i,j\space(i\ne j) such that A_{P_i}=A_{P_j}.

This would imply, (P_i,P_j,P_i,\dots) is an interesting sequence which is **not** a subsequence of P.

Take for example N=3,L=3 and A=\{5,5,5\}.

The solution discussed earlier would yield answer 1. However, the best sequence is (1,3,1) with cost 2.

Thus, we have to handle the case where equality holds separately. Imagine there exists integers i,j such that, A_{P_i}=A_{P_j} and i\ne j.

**Claim :** An optimal interesting sequence with maximal cost, where the first two elements are P_i and P_j is (P_i,P_j,P_i,P_j,P_i,\dots)

## Proof

The proof is simple.

The cost of an interesting sequence where the first two elements are P_i and P_j can **never** exceed |P_i-P_j|. Thus (P_i,P_j,P_i,\dots) is an optimal interesting sequence as the cost is ensured to not fall below |P_i-P_j|, which is the maximum possible cost.

So, we consider all pairs P_i,P_j such that A_{P_i}=A_{P_j}, and determine the maximal possible value of |P_j-P_i|. Call this value low.

We then set low as the lower bound of our search space and then binary search, as we now know that there exists an interesting sequence with cost greater than or equal to low.

# SOLUTION SNIPPET:

```
bool Possible(vii A, int delta, int N, int L){
vi DP(N, 1); //Base case DP[] = 1
for(int x = 1; x < N; x++){
for(int i = 0; i < x; i++){
if(abs(A[x].second - A[i].second) >= delta){
//If Absolute difference >= delta
DP[x] = max(DP[x], DP[i] + 1);
//DP recurrence relation
}
}
if(DP[x] >= L) //Interesting sequence with cost >= delta found
return 1;
}
return 0; //Not possible to have cost >= delta
}
```

```
vii A(N); //Vector of pairs
for(int x = 0; x < N; x++){
cin >> A[x].first;
A[x].second = x;
}
sort(A.rbegin(), A.rend()); //Sort in decreasing order
int low = 0; //Lower bound for the binary search
for(int x = 0; x < N; x++){
for(int i = x + 1; i < N; i++){
if(A[x].first != A[i].first) break;
//If non-distinct elements exist
low = max(low, abs(A[x].second - A[i].second));
}
}
int left = low, right = N - 1; //The upper bound on the cost
while(left < right){
int mid = (left + right + 1) / 2;
// Ceil(a/b) is equivalent to (a + b - 1) / b
//Implementation Trick
if(Possible(A, mid, N, L)) left = mid; //Possible
else right = mid - 1; //Not possible
}
cout << left << endl; //The answer!
```

# TIME COMPLEXITY:

Sorting the input array takes O(N\log N)

Finding the lower bound `low`

takes O(N^2) time as there are 2 nested loops iterating over the sorted array.

There are at max, O(\log N) calls to function `Possible()`

as the search space is reduced by half after each query. Function `Possible()`

takes O(N^2) time as discussed in the **EXPLANATION** section.

Thus, the overall complexity is

# SOLUTIONS:

Editorialistâ€™s solution can be found here.

# SIMILAR PROBLEMS:

Did you like the editorial? Do you have any other approaches to the problem? Any suggestions? Comment them below!

*Experimental:* For better evaluation of my editorials, I request all readers to rate the editorial (on a scale from 1-5, where 5 represents an awesome editorial)

- 1
- 2
- 3
- 4
- 5

0 voters

Also donâ€™t forget to up-vote this post if you liked it !