資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告