Auto comment: topic has been updated by FO7 (previous revision, new revision, compare).

Auto comment: topic has been updated by FO7 (previous revision, new revision, compare).

Can you give me link of problem?

Maybe this will work:

Let F(i, j) be the largest length of a subsequence ending at the i-th index with at most j not equal adjacent elements.

F(i, j) = max( F(s, j), F(s, j-(a[i] != a[s])) + 1) , for 0 <= s < i.

Time complexity O(n^3).

Longest subsequence with at most $$$k$$$ non-equalling elements?

$$$dp_{i,p,j} = $$$ Longest subsequence with $$$k$$$ non-equalling elements, ending with element $$$p$$$

$$$dp_{i,p,j} = max(dp_{i,p,j}, dp_{i-1,p,j})$$$

$$$dp_{i,a_i,j} = max(dp_{i,a_i,j}, dp_{i-1,p,j-(a_i \neq p)}+1))$$$

Time Complexity: $$$O(n^3)$$$

Memory Complexity: can be optimized to be $$$O(n^2)$$$, probably $$$O(n)$$$

My idea is something along the line of this:

First, compress the array such that if it has $$$m$$$ distinct elements, all the elements are numbered from $$$0$$$ to $$$m-1$$$. Let $$$dp_{i,j}$$$ be longest subsequence such that the last element is $$$i$$$ and there are at most $$$j$$$ non equal pairs of adjacent element. Ofc, initially $$$dp_{i,j}=0$$$ for all $$$0 \leq i \leq m-1$$$ and $$$0 \leq j \leq k$$$.

Iterate the array from the $$$1$$$-st element to the $$$n$$$-th element and at the $$$i$$$-th transition, it goes like this:

• $$$dp_{a_i,0} := dp_{a_i,0}+1$$$
• $$$dp_{a_i,j} := \max (dp_{a_i,j},\max(dp_{c,j-1}))+1$$$ for $$$1 \leq j \leq k$$$ and $$$0 \leq c \leq m-1$$$

The complexity of this would be $$$O(nmk)$$$, but I think it could be either optimized to $$$O(nk \log m)$$$ or $$$O(nk)$$$. Also note that this $$$dp$$$ will only return the length of the longest subsequence. If you want to extract the subsequence, put the index information of previous $$$dp$$$ that gives maximum value during transition and then after all the elements have been processed, work backwards from any $$$dp$$$ with largest value to find the subsequence.

I think we can solve with simple recursion + memoization.we will track previous element and count of adjacent equal element with help of previously choosen element.Sorry if bad explanation.

Auto comment: topic has been updated by FO7 (previous revision, new revision, compare).

Auto comment: topic has been updated by FO7 (previous revision, new revision, compare).

Auto comment: topic has been updated by FO7 (previous revision, new revision, compare).

Auto comment: topic has been updated by FO7 (previous revision, new revision, compare).

First let's split the array into continuous segments of equal valuse so insted of a1,a2..,an we will have (a1=a2=...=ai)(ai+1=ai+2=....).....(ak=ak+1=..=an) we can see that a solution picking the first element from each group will have 0 pairs o adjacent elements equal (since adjacent groups have diffrent vaues) and then we can simply add any k elements that are not first in their grup .This is optimal because the answer will be number of grupos +k .Our answer (the lenght) will be number of diffrent adjacent pairs(<=number of groups)+ number of equaladjacent pairs(<=k),so our solution min(n, whit number of groups +k) lenght will be optimal.This can be easly solved in O(n).

FO7 can you kindly provide the optimized code

Time Complexity O(n*k), tested with naive O(n^2*k) dp.

arr=[1,1,2,3,2,1]
k=2

dp={i:[0,set(),Counter()] for i in range(k+1)}

for i in arr:
    prev=0
    for j in range(k+1):

        cur=max(prev+1,(dp[j][0]+1)*(i in dp[j][1]),dp[j][2][i]+1)       

        prev,dp[j][2][i]=dp[j][0],cur

        if dp[j][0]<cur:
           dp[j][:]=[cur,set(]

        if cur==dp[j][0]: 
           dp[j][1].add(i)    

return dp[k][0]

Here is my attempt to the question.

int main() { int n,k; cin>>n>>k; vectorvalues; for(int i=0;i<n;i++) { int x; cin>>x; values.push_back(x); } vector<vector>dp(n+1,vector(k+1,0)); unordered_map<int,unordered_map<int,int>>mp; unordered_map<int,int>mp1; for(int i=0;i<=k;i++) dp[0][i]=1;

for(int i=0;i<n;i++)
{
    unordered_map<int,int>mp2=mp1;
    for(int j=0;j<=k;j++)
    {   
        //The length of the longest subsequence ending at some index less than i and with the value values[i] with atmost j adjacent unequal values.
        dp[i][j]  = mp[values[i]][j]+1;
        if(j>0)
            dp[i][j] = max(dp[i][j],mp2[j-1]+1); //Pick the maximum of all the values at index from 0 to i-1 with atmost j-1 adjacent unequal numbers.
        //update the maximum length for the current value with atmost j adjacent unequal numbers.
        mp[values[i]][j] = max(mp[values[i]][j],dp[i][j]);
        //update maximum length for all sequences ending at 0 to j with atmost j adjacent unequal characters
        mp1[j] = max(mp2[j],dp[i][j]);
    }

}
cout<<dp[n-1][k]<<endl;

}