# MLIS - Editorial

Setter: Kartik Malik
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta

Easy

# PREREQUISITES:

Longest Increasing Subsequence

# PROBLEM:

Chef received an array A of N integers as a valentine’s day present. He wants to maximize the length of the longest strictly increasing subsequence by choosing a subarray and adding a fixed integer X to all its elements.

More formally, Chef wants to maximize the length of the longest strictly increasing subsequence of A by performing the following operation at most once:

• Pick 3 integers L, R and X \ (1 \leq L \leq R \leq N, \ X \in \mathbb{Z}) and assign A_i := A_i + X \ \forall \ i \in [L, R].

Find the length of the longest strictly increasing sequence Chef can obtain after performing the operation at most once.

# EXPLANATION:

Let say that the Chef has chosen L, R and X, and have assigned A_i := A_i + X \ \forall \ i \in [L, R] to get the optimal answer. Also, assume that X \gt 0 for the current discussion. We will handle the other case later. So we can divide our array into three parts: A[1 \ldots L-1], A[L \ldots R], A[R+1 \ldots N]

Now, let say B = \{A_{i_1} \ldots A_{i_x}, A_{j_1} \ldots A_{j_y}, A_{k_1} \ldots A_{k_z} \} be the final LIS, such that i_u \in [1, L-1], j_u \in [L, R], k_u \in [R+1, N]. Observe that if we further increase all A_i for R \lt i \leq N, the length of resulting LIS will either remain same as that of B, or it will increase. In simple words, increasing all A_i for R \lt i \leq N only improves our solution.

So we can claim that if X \geq 0, we will only increase a suffix in the optimal case. If X \lt 0, we can have a similar analysis to show that we will only decrease the prefix, which is equivalent to increasing the remaining suffix by same amount, as long as LIS is considered. So, we only need to analyze X \geq 0, and R = N.

Let us now try to analyze what happens when we fix L. What is the maximum length of LIS that we can get. Now, we can divide our array into two parts: A[1 \ldots L-1], A[L \ldots N].

Let B_1 = \{A_{i_1} \ldots A_{i_x} \} and B_2 = \{ A_{j_1} \ldots A_{j_y} \} be the LIS of A[1 \ldots L-1] and A[L \ldots N] respectively. If we choose X in such a way that A_{i_x} \lt A_{j_1} + X, we can have our final LIS as B_1 + B_2, where the + sign denotes the concatenation. Observe that this is the maximum length of LIS that we can get for this specific L.

Hence, for each i such that 1 \leq i \leq N, we can first calculate dp_1[i] = Length of LIS of A[1 \ldots i] and dp_2[i] = Length of LIS of A[i \ldots N], and take the maximum of dp_1[i] + dp_2[i+1] for all valid i.

# TIME COMPLEXITY:

To calculate length of LIS for each i, we will require O(N \cdot \log{N}) time. To further calculate answer, we will require O(N) time. Hence the overall time complexity is O(N \cdot \log{N}) for each test case.

# SOLUTION:

3 Likes

Why the difficulty for this problem is mentioned as Cakewalk?
At least, mention it as a medium level problem.

13 Likes

Not sure if it is medium, I guess should be Easy at least, definitely not a cakewalk!

1 Like

Anyone having difficulty in understanding can checkout my explanation. Hope it will help

2 Likes

Sorry it was a mistake… Updated.

2 Likes

Can someone help me out in this code?

vector<int>a;
int n;
void solve()
{
cin>>n;
a.clear();
a.resize(n);
for(int i=0;i<n;i++)
cin>>a[i];

int ans=0;
int len1=1;
int len2=1;
int stop=0;
for(int i=1;i<n;i++)
{
if(a[i]>a[i-1])
len1++;
else{
for(int j=i+1;j<n;j++)
{
if(a[j]>a[j-1])
len2++;
else{
ans=max(ans,len1+len2);
i=j-1;
len1=len2;
len2=1;
break;
}
}
ans=max(ans,len1+len2);
}
}
cout<<ans;
}


solved it using fenwick tree kind of overkill . Btw cool problem here is my submission
https://www.codechef.com/viewsolution/60651061

1 Like

What will be its time complexity??

I tried using the concept of hashing to solve this problem.
First I mapped how an element is (> or < or == ) wrt to its’s prev element.
1 for increasing
0 for same
-1 for decreasing

Example: 1 2 4 3 9 7 16 12 5
Mapped: 1 1 1 -1 1 -1 1 -1 -1
Ans = 5

Example: 2 4 5 6 2 2 7 8 3 4 5 6 7
Mapped: 1 1 1 1 -1 0 1 1 -1 1 1 1 1
Ans = 7

The idea was to select the most extended sequence in this map which contains at most one -1 / 0.

Here is my code.

Kindly someone please point out mistakes in logic with the failed test cases.

N + nlogn + nlogN
where n is size of array and N size of tree which is 2e5
O(N) cause of memset
nlogn cause of compression as elements are larger than 2e5
and nlogN for finding the values using fenwick tree for every index

1 Like

You are finding longest strictly increasing subarray,I was doing the same mistake.

1 Like

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
ll t;
cin >> t;
while(t--) {
ll n;
cin >> n;
vector<ll>arr(n);
for(ll i = 0; i < n; i++) {
cin >> arr[i];
}

vector<ll>dp(n),revdp(n);
vector<ll>res;

// dp1
for(ll i = 0; i < n; i++) {
if(res.empty() or arr[i] > res.back()) res.push_back(arr[i]);
else *upper_bound(res.begin(),res.end(),arr[i]) = arr[i];
dp[i] = res.size();
}

// dp2
reverse(arr.begin(),arr.end());
for(ll i = 0; i < n; i++) arr[i] = -arr[i];
res.clear();
for(ll i = 0; i < n; i++) {
if(res.empty() or arr[i] > res.back()) res.push_back(arr[i]);
else *lower_bound(res.begin(),res.end(),arr[i]) = arr[i];
revdp[i] = res.size();
}
reverse(revdp.begin(),revdp.end());

for(ll i = 1; i < n; i++) dp[i] = max(dp[i], dp[i-1]);
for(ll i = n-2; i >= 0; i--) revdp[i] = max(revdp[i], revdp[i+1]);

ll ans = dp[n-1];
for(ll i = 0; i < n-1; i++) ans = max(ans, dp[i]+revdp[i+1]);

cout << ans << endl;
}
return 0;
}


When I was trying to solve this problem, I came up with some TCs and realized we can only increase the LIS once if the LIS of the original array is less than n(size of the array) i.e. if size of LIS(original arr) == n then ans is n else ans is (size of LIS(original array) + 1). But I guess this is wrong so can anyone give a testcase where the size of LIS is increased by more than 1 than the original LIS’s size?

A = [10 11 12 13 1 2 3]

take the last three elements of the array and add x = 100 to them, the new subarray becomes [10 11 12 13 101 102 103] and its LIS = 7, while LIS of original array was 4.

1 Like

Can anyone help me with the following code:
In the code I am traversing the array and storing the all the max length of subarrays that are in strictly increasing sequence into a list called lis. Then I am finding the max of sum of length of 2 consecutive subarrays in increasing sequence.
For example:

1. if input array = [1, 2, 2, 1] then lis array = [2, 1, 1] as the subarrays with increasing sequence are [1,2], [2] and [1] and max of sum of 2 consecutive elements is 3.
2. If input array = [1, 2, 4, 3, 9, 7, 16, 12, 5], then lis = [3, 2, 2, 1, 1] as the subarrays with increasing sequence are [1, 2, 4], [3, 9], [7, 16]. [12] and [5]. Then taking a max of sum of 2 consecutive elements which is 5 in this case.

But I am getting wrong answer for it although it passing the sample test cases. Please help me in understanding the incorrectness in logic/code.

tc = int(input())
for i in range(tc):
n = int(input())
arr = list(map(int, input().split()))
lis = []
count = 0
for j in range(n):
if j == 0:
count += 1
elif arr[j - 1] < arr[j]:
count += 1
else:
lis.append(count)
count = 1
lis.append(count)
max_sum = lis[0]
for j in range(len(lis) - 1):
if lis[j] + lis[j + 1] > max_sum:
max_sum = lis[j] + lis[j + 1]
print(max_sum)

1 Like

Can anyone please share some more problems where we can find the suffix array by multiplying the whole array with -1? Actually, I have never seen this thing before and I’m not getting the intuition behind this. I was also able to figure out the approach in the contest but was not able to find this suffix array.
Any kind of help will be appreciated.