数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中最多翻转K个数组元素的最大子数组和
在这个问题中，我们给定一个数组和一个整数k。我们的任务是编写一个C++程序，找到通过最多翻转k个数组元素的符号来获得的最大子数组和。
代码描述 − 在这里，我们必须找到最多k个需要在数组中翻转的元素，这将使由该数组创建的子数组的和最大。
让我们举个例子来理解这个问题：
输入 − array = {1, -2, 7, 0} k = 2
输出 − 10
解释 − 我们只翻转一个元素-2，使得数组和为10，这是可能的最大值。
为了解决这个问题，我们将使用动态规划方法，该方法将找到从第i个索引到第j个索引的数组的最大可能和，并将其存储在数组maxSumij[i][j]中，并考虑元素翻转或不翻转这两种情况，这将返回最佳情况，这将使用对函数的递归调用来完成。最后，我们将从maxSumij[i][j]矩阵中找到最大元素。
示例
程序演示了我们解决方案的工作原理：
#include <bits/stdc++.h>
using namespace std;
#define right 2
#define left 4
int arraySumij[left][right];
int findSubarraySum(int i, int flips, int n, int a[], int k){
if (flips > k)
return -1e9;
if (i == n)
return 0;
if (arraySumij[i][flips] != -1)
return arraySumij[i][flips];
int maxSum = 0;
maxSum = max(0, a[i] + findSubarraySum(i + 1, flips, n, a, k));
maxSum = max(maxSum, -a[i] + findSubarraySum(i + 1, flips + 1, n, a, k));
arraySumij[i][flips] = maxSum;
return maxSum;
}
int maxSubarraySumFlip(int a[], int n, int k){
memset(arraySumij, -1, sizeof(arraySumij));
int maxSum = -100;
for (int i = 0; i < n; i++)
maxSum = max(maxSum, findSubarraySum(i, 0, n, a, k));
return maxSum;
}
int main() {
int a[] = {-3, 56, -1, 8};
int n = sizeof(a) / sizeof(a[0]);
int k = 2;
cout<<"Maximum subarry sum by fipping signs of at most "<<k<<" element is "<<maxSubarraySumFlip(a, n, k);
return 0;
}输出
Maximum subarry sum by fipping signs of at most 2 element is 66
更新于: 2020年6月3日
340 次浏览
广告