Maximum product of an increasing subsequence

Problem Statement

The problem “Maximum product of an increasing subsequence” states that you are given an array of integers. Now you need to find out the maximum product you can achieve such that you multiply the elements of an increasing subsequence. The thing to note is that, we are not supposed to find out the longest increasing subsequence. We may have a smaller subsequence but it should have the maximum product.

Example

10, 1, 1000, 2, 3, 4

10000

The maximum product of an increasing subsequence is 10, 1000. Even though the longest increasing subsequence is {1, 2, 3, 4}.

Approach

The problem resembles the Longest Increasing Subsequence Problem. The slight modification over that problem is that instead of finding the longest increasing subsequence. We need to find the maximum product of an increasing subsequence.

So, to solve this problem. We can use Brute Force Approach to solve the problem as well. Even though this method is inefficient but should be known. So, in the brute force approach, we will first generate all the subsequences. After generating the subsequences, we create a checker function. In the checker function, we check if the subsequence is valid. The validity of the checker function means that the subsequence should be an increasing subsequence. After that, we keep on updating the maximum product found from the increasing subsequence.

Now the question is how do we solve the problem efficiently? To solve the problem efficiently, we use Dynamic Programming. The transition in the problem is the same as that of the LIS problem. Our DP array stores the maximum product that can be attained if we considered all the elements until the current element. And there is one more condition that the subsequence should contain the current element. Then for calculating the DP array we run a nested loop in a backward direction from the current element to the starting element. If we find an element that is smaller than the current element then we update our answer if multiplying the current element to the element at that index in the DP array is greater than the value currently stored.

Code

C++ code to find Maximum product of an increasing subsequence

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


int maxProductOfIncreasingSubsequence(vector<int> &input){
  vector<int> dp(n);
  dp[0] = input[0];
  int ans = input[0];
  for(int i=1;i<n;i++){
    for(int j=0;j<i;j++){
      if(input[j] < input[i])
        dp[i] = max(dp[i], dp[j]*input[i]);
    }
    ans = max(ans, dp[i]);
  }
  return ans;
}

int main(){
  int n;cin>>n;
  vector<int> input(n);
  for(int i=0;i<n;i++)
    cin>>input[i];

  cout<<maxProductOfIncreasingSubsequence(input);
}

6
10 1 1000 2 3 4

10000

Java code to find Maximum product of an increasing subsequence

import java.util.*;

class Main{
    static int maxProductOfIncreasingSubsequence(ArrayList<Integer> input){
    ArrayList<Integer> dp = new ArrayList<Integer>();
    dp.add(input.get(0));
    int ans = input.get(0);
    int n = input.size();
    for(int i=1;i<n;i++){
      dp.add(input.get(i));
      for(int j=0;j<i;j++){
        if(input.get(j) < input.get(i))
          dp.set(i, Math.max(dp.get(i), dp.get(j)*input.get(i)));
      }
      ans = Math.max(ans, dp.get(i));
    }
    return ans;
  }

  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ArrayList<Integer> input = new ArrayList<>();
    for(int i=0;i<n;i++){
      int in = sc.nextInt();
      input.add(in);
    }

    int answer = maxProductOfIncreasingSubsequence(input);
    System.out.print(answer);
  }
}

6
10 1 1000 2 3 4

10000

Complexity Analysis

Time Complexity

O(N^2) because we are using two nested loops. One which runs over all the elements and the other inner loop runs over all the elements until the current element.

Space Complexity

O(N) because we create a single-dimensional DP table. Thus space complexity is linear.