子序列增加的最大乘积


难度级别 易得奖学金
经常问 ol石 GE医疗集团 HackerRank IBM Snapchat 雅虎
排列 动态编程

问题陈述

问题“增加的子序列的最大乘积”指出给您一个整数数组。 现在,您需要找出可以实现的最大乘积,从而乘以不断增加的子序列的元素。 需要注意的是,我们不应找出最长的增长子序列。 我们的子序列可能较小,但应具有最大乘积。

使用案列

子序列增加的最大乘积

10, 1, 1000, 2, 3, 4
10000

递增子序列的最大乘积是10,1000。即使最长的递增子序列是{1}。

途径

问题类似于 最长递增子序列 问题。 对这个问题的轻微修改是,它没有找到最长的增长子序列。 我们需要找到增加的子序列的最大乘积。

所以,要解决这个问题。 我们也可以使用蛮力方法来解决该问题。 即使此方法效率低下,但也应为人们所熟知。 因此,在蛮力方法中,我们将首先生成所有子序列。 生成子序列后,我们创建一个检查器函数。 在检查器功能中,我们检查子序列是否有效。 检查器功能的有效性意味着该子序列应该是一个递增的子序列。 之后,我们继续更新从不断增加的子序列中找到的最大乘积。

现在的问题是,我们如何有效地解决问题? 为了有效地解决问题,我们使用动态编程。 问题中的过渡与LIS问题中的过渡相同。 我们的DP数组存储了如果考虑所有元素直到当前元素,则可以获得的最大乘积。 还有一个条件是子序列应包含当前元素。 然后,为了计算DP数组,我们在从当前元素到起始元素的反向方向上运行了一个嵌套循环。 如果找到一个小于当前元素的元素,则将当前元素与DP数组中该索引处的元素相乘的值大于当前存储的值,则我们将更新答案。

代码

C ++代码查找递增子序列的最大乘积

#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代码查找子序列增加的最大乘积

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

复杂度分析

时间复杂度

O(N ^ 2),因为我们使用了两个嵌套循环。 一个运行在所有元素上,另一个内部循环运行在所有元素上,直到当前元素为止。

空间复杂度

O(N),因为我们创建了一维DP表。 因此,空间复杂度是线性的。