資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中最多反轉兩個元素後的最大子陣列和
在這個問題中，我們給定一個數組。我們的任務是建立一個程式，該程式將找到在 C++ 中最多反轉兩個元素後的最大子陣列和。
問題描述 - 在這裡，我們必須找到反轉陣列中任意兩個數字的符號後產生最大和的子陣列。
讓我們舉個例子來理解這個問題，
輸入 - 陣列 = {-5, 1, 3, 8, -2, 4, 7}
輸出 - 30
解釋 - 我們將考慮從索引 0 到 6 的元素，並將值 -5 和 -2 反轉以獲得具有最大和的陣列。
為了解決這個問題，我們將使用動態規劃方法。我們將檢查大小為 1 到 n（陣列長度）的所有子陣列的最大和。因此，對於每個子陣列，我們有三種情況 -
情況 1 - 反轉子陣列的兩個元素後的子陣列的最大和。
情況 2 - 反轉子陣列的一個元素後的子陣列的最大和。
情況 3 - 反轉子陣列的零個元素後的子陣列的最大和。
因此，對於我們擁有的每次迭代，我們將找到陣列的最大和以及當前元素的最大值，並將其初始化為最大值。
我們將最大和儲存到一個名為 maxSum 的二維陣列中。最終的 maxSum 是二維陣列中所有元素的最大值。
示例
顯示我們解決方案實現的程式，
#include <bits/stdc++.h>
using namespace std;
int findMaxSubarraySum(int a[], int n) {
int maxSubarraySum = 0;
int* arr = new int[n + 1];
for (int i = 1; i <= n; i++)
arr[i] = a[i - 1];
int** maxSum = new int*[n + 1];
for (int i = 0; i <= n; i++)
maxSum[i] = new int[3];
for (int i = 1; i <= n; ++i) {
maxSum[i][0] = max(arr[i], maxSum[i - 1][0] + arr[i]);
maxSum[i][1] = max(0, maxSum[i - 1][0]) - arr[i];
if (i >= 2)
maxSum[i][1] = max(maxSum[i][1], maxSum[i - 1][1] + arr[i]);
if (i >= 2)
maxSum[i][2] = maxSum[i - 1][1] - arr[i];
if (i >= 3)
maxSum[i][2] = max(maxSum[i][2], maxSum[i - 1][2] + arr[i]);
maxSubarraySum = max(maxSubarraySum, maxSum[i][0]);
maxSubarraySum = max(maxSubarraySum, maxSum[i][1]);
maxSubarraySum = max(maxSubarraySum, maxSum[i][2]);
}
return maxSubarraySum;
}
int main(){
int arr[] = {-5, 1, 3, 8, -2, 4, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum subarray sum after inverting at most two elements is "<<findMaxSubarraySum(arr, n);
return 0;
}輸出
Maximum subarray sum after inverting at most two elements is 30
更新於: 2020年6月3日
195 次檢視
廣告