Given an array arr[] of N positive integers, the task is to find the largest strictly increasing subsequence of arr[] such that the indices of the selected elements in arr[], and the selected elements are multiples of each other individually.
Note: Consider 1 based indexing for the array arr[].
Examples:
Input: arr[] = {1, 4, 2, 3, 6, 4, 9}
Output: 3
Explanation:
We can choose index 1, 3, 6 and values are 1, 2, 4:
Here every greater index is divisible by smaller index and every greater index value is greater than the smaller index value.
Input: arr[] = {5, 3, 4, 6}
Output: 2
Explanation:
We can choose index 1 and 3 and values are 3 and 6:
Here, every greater index is divisible by smaller index and every greater index value is greater than the smaller index value.
Naive Approach:
The naive approach is to simply generate all possible subsequence and for each subsequence check two conditions:
- first check if elements are in strictly increasing order and
- secondly check if the index of the selected elements in arr[] is multiple of each other.
Out of all possible subsequence which satisfies the given two conditions select the largest subsequence.
Time Complexity: O( N * 2N )
Auxiliary Space: O( N )
Efficient Approach:
We can optimize the code by using Dynamic Programming by avoiding redundant calculation of the repeated sub problem by caching its result.
- Create an array dp[] of size equal to the size of arr[], where dp[i] represents size of largest subsequence till i-th index which satisfies the given conditions.
- Initialize array dp[] with 0.
- Now, iterate the array arr[] from the end.
- For each index find the indices j which divide the current index and check if the value at current index is greater than the element at index j.
- If it is then update dp[j] as:
dp[j] = max(dp[current] + 1, dp[j])
Finally, traverse the array dp[] and print the maximum value.
Below is the implementation of the efficient approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function that print maximum length// of arrayvoid maxLength(int arr[], int n){ // dp[] array to store the // maximum length vector<int> dp(n, 1); for (int i = n - 1; i > 1; i--) { // Find all divisors of i for (int j = 1; j <= sqrt(i); j++) { if (i % j == 0) { int s = i / j; if (s == j) { // If the current value // is greater than the // divisor's value if (arr[i] > arr[s]) { dp[s] = max(dp[i] + 1, dp[s]); } } else { // If current value // is greater // than the divisor's value // and s is not equal // to current index if (s != i && arr[i] > arr[s]) dp[s] = max(dp[i] + 1, dp[s]); // Condition if current // value is greater // than the divisor's value if (arr[i] > arr[j]) { dp[j] = max(dp[i] + 1, dp[j]); } } } } } int max = 0; // Computing the greatest value for (int i = 1; i < n; i++) { if (dp[i] > max) max = dp[i]; } // Printing maximum length of array cout << max << "\n";}// Driver Codeint main(){ // Given array arr[] int arr[] = { 0, 1, 4, 2, 3, 6, 4, 9 }; int size = sizeof(arr) / sizeof(arr[0]); // Function Call maxLength(arr, size); return 0;} |
Java
// Java program for the above approach import java.util.*;import java.io.*;class GFG{ // Function that print maximum length// of arraystatic void maxLength(int arr[], int n){ // dp[] array to store the // maximum length int dp[] = new int[n]; for(int i = 1; i < n; i++) { dp[i] = 1; } for(int i = n - 1; i > 1; i--) { // Find all divisors of i for(int j = 1; j <= Math.sqrt(i); j++) { if (i % j == 0) { int s = i / j; if (s == j) { // If the current value // is greater than the // divisor's value if (arr[i] > arr[s]) { dp[s] = Math.max(dp[i] + 1, dp[s]); } } else { // If current value is greater // than the divisor's value // and s is not equal // to current index if (s != i && arr[i] > arr[s]) dp[s] = Math.max(dp[i] + 1, dp[s]); // Condition if current // value is greater // than the divisor's value if (arr[i] > arr[j]) { dp[j] = Math.max(dp[i] + 1, dp[j]); } } } } } int max = 0; // Computing the greatest value for(int i = 1; i < n; i++) { if (dp[i] > max) max = dp[i]; } // Printing maximum length of array System.out.println(max);}// Driver Codepublic static void main(String[] args){ // Given array arr[] int arr[] = { 0, 1, 4, 2, 3, 6, 4, 9 }; int size = arr.length; // Function call maxLength(arr, size);}}// This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approachfrom math import *# Function that print maximum length # of arraydef maxLength (arr, n): # dp[] array to store the # maximum length dp = [1] * n for i in range(n - 1, 1, -1): # Find all divisors of i for j in range(1, int(sqrt(i)) + 1): if (i % j == 0): s = i // j if (s == j): # If the current value # is greater than the # divisor's value if (arr[i] > arr[s]): dp[s] = max(dp[i] + 1, dp[s]) else: # If current value # is greater # than the divisor's value # and s is not equal # to current index if (s != i and arr[i] > arr[s]): dp[s] = max(dp[i] + 1, dp[s]) # Condition if current # value is greater # than the divisor's value if (arr[i] > arr[j]): dp[j] = max(dp[i] + 1, dp[j]) Max = 0 # Computing the greatest value for i in range(1, n): if (dp[i] > Max): Max = dp[i] # Printing maximum length of array print(Max)# Driver Codeif __name__ == '__main__': # Given array arr[] arr = [ 0, 1, 4, 2, 3, 6, 4, 9] size = len(arr) # Function call maxLength(arr, size)# This code is contributed by himanshu77 |
C#
// C# program for the above approach using System;class GFG{ // Function that print maximum length// of arraystatic void maxLength(int[] arr, int n){ // dp[] array to store the // maximum length int[] dp = new int[n]; for(int i = 1; i < n; i++) { dp[i] = 1; } for(int i = n - 1; i > 1; i--) { // Find all divisors of i for(int j = 1; j <= Math.Sqrt(i); j++) { if (i % j == 0) { int s = i / j; if (s == j) { // If the current value // is greater than the // divisor's value if (arr[i] > arr[s]) { dp[s] = Math.Max(dp[i] + 1, dp[s]); } } else { // If current value is greater // than the divisor's value // and s is not equal // to current index if (s != i && arr[i] > arr[s]) dp[s] = Math.Max(dp[i] + 1, dp[s]); // Condition if current // value is greater // than the divisor's value if (arr[i] > arr[j]) { dp[j] = Math.Max(dp[i] + 1, dp[j]); } } } } } int max = 0; // Computing the greatest value for(int i = 1; i < n; i++) { if (dp[i] > max) max = dp[i]; } // Printing maximum length of array Console.WriteLine(max);}// Driver Codepublic static void Main(){ // Given array arr[] int[] arr = new int[] { 0, 1, 4, 2, 3, 6, 4, 9 }; int size = arr.Length; // Function call maxLength(arr, size);}}// This code is contributed by sanjoy_62 |
Javascript
<script>// Javascript Program to implement// the above approach// Function that print maximum length// of arrayfunction maxLength(arr, n){ // dp[] array to store the // maximum length let dp = []; for(let i = 1; i < n; i++) { dp[i] = 1; } for(let i = n - 1; i > 1; i--) { // Find all divisors of i for(let j = 1; j <= Math.sqrt(i); j++) { if (i % j == 0) { let s = i / j; if (s == j) { // If the current value // is greater than the // divisor's value if (arr[i] > arr[s]) { dp[s] = Math.max(dp[i] + 1, dp[s]); } } else { // If current value is greater // than the divisor's value // and s is not equal // to current index if (s != i && arr[i] > arr[s]) dp[s] = Math.max(dp[i] + 1, dp[s]); // Condition if current // value is greater // than the divisor's value if (arr[i] > arr[j]) { dp[j] = Math.max(dp[i] + 1, dp[j]); } } } } } let max = 0; // Computing the greatest value for(let i = 1; i < n; i++) { if (dp[i] > max) max = dp[i]; } // Printing maximum length of array document.write(max);}// Driver Code // Given array arr[] let arr = [ 0, 1, 4, 2, 3, 6, 4, 9 ]; let size = arr.length; // Function call maxLength(arr, size); // This code is contributed by chinmoy1997pal.</script> |
Output:
3
Time Complexity: O(N*(sqrt(N)) Since, for each index of the array, we calculate its all divisor, this takes O(sqrt(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
