資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中刪除最多一個元素的最大子陣列和
在這個問題中，我們得到一個數組。我們的任務是建立一個程式，該程式將在 C++ 中找到刪除最多一個元素的最大子陣列和。
基本上，我們需要找到一個元素，當刪除該元素時，陣列中剩餘元素的總和最大。
讓我們舉一個例子來理解這個問題，
輸入 − 陣列 = {5, 1, 9, 2, -1, 7}
輸出 − 24
說明 − 我們從陣列中刪除了 -1，並且總和成為所有可能結果中的最大值。
解決此問題的一種方法是找到陣列的最小元素，然後找到陣列中所有剩餘元素的總和。
但是在這裡，沒有應用元素刪除條件，Kadane 演算法將以更好的方式解決問題。因此，在這裡我們將計算最大和，這樣我們將從開始到第 i 個元素以及從結束到第 i 個元素計算和。
然後檢查使用開始和結束和陣列跳過哪個第 i 個元素，然後列印跳過給定元素後的和。
示例
程式演示了我們解決方案的實現，
#include <bits/stdc++.h>
using namespace std;
int maxSubarraySum(int array[], int n){
int startSum[n], endSum[n];
int maxSum = array[0], overAllMax = array[0];
startSum[0] = array[0];
for (int i = 1; i < n; i++){
maxSum = max(array[i], maxSum + array[i]);
overAllMax = max(overAllMax, maxSum);
startSum[i] = maxSum;
}
maxSum = endSum[n-1] = array[n-1];
for (int i = n-2; i >= 0; i--){
maxSum = max(array[i], maxSum + array[i]);
overAllMax = max(overAllMax, maxSum);
endSum[i] = maxSum;
}
int SubArraySum = overAllMax;
for (int i = 1; i < n - 1; i++)
SubArraySum = max(SubArraySum, startSum[i - 1] + endSum[i + 1]);
return SubArraySum;
}
int main()
{
int array[] = {5, 7, 1, -1, 4, 2, 9};
int n = sizeof(array) / sizeof(array[0]);
cout<;"The maximum subarray after removing one element is "<<maxSubarraySum(array, n);
return 0;
}輸出
The maximum subarray after removing one element is 28
更新於: 2020-06-03
126 次瀏覽
廣告