資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時裝學
法學C++ 程式中遞增子序列的最大乘積
在這個問題中，我們得到了一個長度為 n 的陣列 arr[]。我們的任務是找到遞增子序列的最大乘積。
問題描述 − 我們需要從陣列元素中找到任意大小的遞增子序列的最大乘積。
讓我們舉個例子來理解這個問題，
輸入
arr[] = {5, 4, 6, 8, 7, 9}輸出
2160
說明
All Increasing subsequence:
{5,6,8,9}. Prod = 2160
{5,6,7,9}. Prod = 1890
Here, we have considered only max size subsequence.解決方法
解決這個問題的一個簡單方法是使用動態規劃的方法。為此，我們將儲存到給定陣列元素為止的最大乘積的遞增子序列，然後儲存在一個數組中。
演算法
初始化 −
prod[] with elements of arr[]. maxProd = −1000
步驟 1 −
Loop for i −> 0 to n−1
步驟 1.1 −
Loop for i −> 0 to i
步驟 1.1.1
Check if the current element creates an increasing subsequence i.e. arr[i]>arr[j] and arr[i]*prod[j]> prod[i] −> prod[i] = prod[j]*arr[i]
步驟 2 −
find the maximum element of the array. Following steps 3 and 4.
步驟 3 −
Loop form i −> 0 to n−1
步驟 4 −
if(prod[i] > maxProd) −> maxPord = prod[i]
步驟 5 −
return maxProd.
示例
程式展示了我們解決方案的實現，
#include <iostream>
using namespace std;
long calcMaxProdSubSeq(long arr[], int n) {
long maxProdSubSeq[n];
for (int i = 0; i < n; i++)
maxProdSubSeq[i] = arr[i];
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && maxProdSubSeq[i] <
(maxProdSubSeq[j] * arr[i]))
maxProdSubSeq[i] = maxProdSubSeq[j] * arr[i];
long maxProd = −1000 ;
for(int i = 0; i < n; i++){
if(maxProd < maxProdSubSeq[i])
maxProd = maxProdSubSeq[i];
}
return maxProd;
}
int main() {
long arr[] = {5, 4, 6, 8, 7, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum product of an increasing subsequence is "<<calcMaxProdSubSeq(arr, n);
return 0;
}輸出
The maximum product of an increasing subsequence is 2160
更新於: 2020 年 12 月 9 日
140 次瀏覽
廣告