home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Maximum product of an increasing subsequence in C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมหาผลคูณสูงสุดของลำดับย่อยที่เพิ่มขึ้น

เราจะได้รับอาร์เรย์จำนวนเต็ม งานคือหาผลคูณสูงสุดของลำดับย่อยใดๆ ของอาร์เรย์ที่มีจำนวนองค์ประกอบเท่าไหร่ก็ได้

ตัวอย่างโค้ด

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

ll lis(ll arr[], ll n) {
    ll mpis[n];
    for (int i = 0; i < n; i++) mpis[i] = arr[i];
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && mpis[i] < mpis[j] * arr[i])
                mpis[i] = mpis[j] * arr[i];
    return *max_element(mpis, mpis + n);
}

int main() {
    ll arr[] = {3, 100, 4, 5, 150, 6};
    ll n = sizeof(arr) / sizeof(arr[0]);
    printf("%lld", lis(arr, n));
    return 0;
}

เอาต์พุต

45000