数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告