Prerequisite : Basic Dynamic Programming.
Problem :- Given a sequence of n integers, find the length of the longest dividing subsequence.
Dividing subsequence property : -
Sequence : - a1,a2,a3,a4,a5,a6,a7,a9
SubSequence - a1,a4,a6,a9
Dividing property - Each element can divide its following subsequence element(a4%a1==0 and a6%a4==0 and a9%a6==0) .
Explanation :- Dynamic programming is used to break the problem into smaller subproblems. Here we can break it into smaller arrays, for example first solving the problem for a single element, then keep on increasing the length of the array and finding the answer for them.
Algorithm :-
Each state of dp represents the length of the longest increasing subsequence starting from a given point.
Starting from the end of the array, dp[n] = 1 as there will be no following element.
Move from end to front and for each state :-
- Check the preceding state which is divisible by our current state.
- Save the highest value of the state which is divisible + 1 to your current state.
Ex dp[i] = max(dp[i+1],dp[i+4],dp[i+7])- here the element present at (i+1),(i+4) and (i+7)th index are divisible by ith index.
Repeat the above process and print the highest value stored in a state.
Time complexity = O(n*n)
For better understanding you can also refer to IARCS Editorial
Solution :-
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
vector<int>v1(n);
for(int i=0;i<n;i++){
cin>>v1[i];
}
int fans = 1;
vector<int>dp(n+1,1);
for(int i=n-1;i>=0;i--){
for(int j=i+1;j<n;j++){
if(v1[j]%v1[i]==0){
dp[i] = max(dp[i],dp[j]+1);
}
}
fans = max(fans,dp[i]);
}
cout<<fans<<"\n";
// your code goes here
}