ผลิตภัณฑ์สูงสุดของลำดับต่อมาที่เพิ่มขึ้น  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน แอคโคไลท์ GE Healthcare HackerRank ไอบีเอ็ม Snapchat yahoo
แถว การเขียนโปรแกรมแบบไดนามิก

คำชี้แจงปัญหา  

ปัญหา“ ผลคูณสูงสุดของลำดับต่อมาที่เพิ่มขึ้น” ระบุว่าคุณได้รับอาร์เรย์ของจำนวนเต็ม ตอนนี้คุณต้องหาผลิตภัณฑ์สูงสุดที่คุณสามารถทำได้เพื่อให้คุณคูณองค์ประกอบของลำดับต่อมาที่เพิ่มขึ้น สิ่งที่ควรทราบก็คือเราไม่ควรที่จะพบว่าผลต่อเนื่องที่เพิ่มขึ้นยาวนานที่สุด เราอาจมีในภายหลังที่น้อยกว่า แต่ควรมีผลิตภัณฑ์สูงสุด

ตัวอย่าง  

ผลิตภัณฑ์สูงสุดของลำดับต่อมาที่เพิ่มขึ้นหมุด

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

ผลคูณสูงสุดของลำดับต่อมาที่เพิ่มขึ้นคือ 10, 1000 แม้ว่าลำดับต่อมาที่เพิ่มขึ้นยาวนานที่สุดคือ {1, 2, 3, 4}

เข้าใกล้  

ปัญหาคล้ายกับไฟล์ ผลที่ตามมาเพิ่มขึ้นยาวนานที่สุด ปัญหา. การแก้ไขปัญหาเล็กน้อยนั้นก็คือแทนที่จะค้นหาสิ่งที่เพิ่มขึ้นในเวลาต่อมายาวนานที่สุด เราต้องหาผลคูณสูงสุดที่เพิ่มขึ้นในเวลาต่อมา

ดังนั้นเพื่อแก้ปัญหานี้ เราสามารถใช้ Brute Force Approach เพื่อแก้ปัญหาได้เช่นกัน ถึงแม้วิธีนี้จะไม่มีประสิทธิภาพ แต่ก็ควรรู้ไว้ ดังนั้นในแนวทาง brute force เราจะสร้างลำดับต่อมาทั้งหมดก่อน หลังจากสร้างลำดับต่อมาเราจะสร้างฟังก์ชันตัวตรวจสอบ ในฟังก์ชันตัวตรวจสอบเราจะตรวจสอบว่าลำดับต่อมาถูกต้องหรือไม่ ความถูกต้องของฟังก์ชันตัวตรวจสอบหมายความว่าลำดับต่อมาควรเป็นลำดับต่อมาที่เพิ่มขึ้น หลังจากนั้นเราจะทำการอัปเดตผลิตภัณฑ์สูงสุดที่พบในเวลาต่อมาที่เพิ่มขึ้นเรื่อย ๆ

ดูสิ่งนี้ด้วย
คำนำหน้าทั่วไปที่ยาวที่สุดโดยใช้การเรียงลำดับ

ตอนนี้คำถามคือเราจะแก้ปัญหาอย่างมีประสิทธิภาพได้อย่างไร? เพื่อแก้ปัญหาอย่างมีประสิทธิภาพเราใช้ Dynamic Programming การเปลี่ยนแปลงในปัญหาจะเหมือนกับปัญหา 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 แบบมิติเดียว ดังนั้นความซับซ้อนของอวกาศจึงเป็นเชิงเส้น