子序列增加的最大乘積


難度級別 容易獎學金
經常問 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表。 因此,空間複雜度是線性的。