資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中大小為 k 的子序列的最大乘積
在這個問題中，我們給定一個整數陣列 arr[] 和一個數字 k。我們的任務是建立一個程式，在 C++ 中找到大小為 k 的子序列的最大乘積。
問題描述 - 在這裡，我們需要找到大小為 k（1<= k <= n）的子序列，該子序列的元素乘積最大。
讓我們舉一個例子來理解這個問題，
輸入
arr[] = {1, 5, 6, -2, 0, 4} , k = 3輸出
120
解釋
大小為 3 的子序列，其乘積最大的是 (5, 6, 4)。乘積為 120。
解決方案方法
為了解決這個問題，我們將首先對陣列 arr[] 進行排序，然後根據 arr[] 的元素和 k 的值進行處理。方法會根據以下情況發生變化：
情況 1（如果 k 為偶數） - 乘積可以包含所有最大的 k 個值，除了 0。這裡，我們還需要考慮負值對。因為它們的絕對值也可能給出最大結果。
情況 2（如果 k 為奇數） - 這是一個稍微複雜的情況，值決定了結果如何計算。這種情況需要根據陣列的最大元素進一步分類。
情況 2.1（如果最大數為正） - 這意味著陣列是正數和負數的混合。在這種情況下，我們將找到最大的 k 個元素，並從負數側搜尋最大對（如果可能，這可能會給出結果）。
情況 2.2（如果最大數為零） - 這意味著陣列包含所有負元素和零。在這種情況下，最大結果將為 0，因為將奇數個負元素相乘將導致負數，這意味著 0 是最大乘積。
情況 2.3（如果最大數為負） - 這意味著陣列僅包含負數。在這種情況下，最大結果將由乘以最小絕對值的元素提供，即最大陣列將提供幫助。
透過這種方式，我們需要檢查元素的值以及 k 的值。以獲得最佳結果。為此，我們將保持陣列兩側的最大值和最小值，以檢查結果是否可以透過將負數對乘以結果來產生。
程式說明解決方案的工作原理，
示例
#include <bits/stdc++.h>
using namespace std;
int findMaxSubArrayProduct(int arr[], int n, int k) {
sort(arr, arr + n);
int maxProd = 1;
int i = 0, j = 0;
int maxprod, minprod;
if (arr[n - 1] == 0 && (k % 2 == 1))
return 0;
if (arr[n - 1] <= 0 && (k % 2 == 1)) {
for (i = n - 1; i >= n - k; i--)
maxProd *= arr[i];
return maxProd;
}
i = 0;
j = n - 1;
if (k % 2 == 1) {
maxProd *= arr[j];
j--;
k--;
}
k = k/2;
int it = 0;
while(it < k){
int minprod = arr[i] * arr[i + 1];
int maxprod = arr[j] * arr[j - 1];
if (minprod > maxprod) {
maxProd *= minprod;
i += 2;
} else {
maxProd *= maxprod;
j -= 2;
}
it++;
}
return maxProd;
}
int main() {
int arr[] = { 1, 5, 6, -2, 0, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout<<"The maximum product of subsequence of size "<<k<<" is "<<findMaxSubArrayProduct(arr, n, k);
return 0;
}輸出
The maximum product of subsequence of size 3 is 120
更新於: 2020-09-15
400 次瀏覽
廣告