資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 中最大環形子陣列和
給定一個數組，任務是形成子陣列，使得子陣列以迴圈方式相加的結果為最大值。
輸入 − int arr[] = {1, 2, 8, 4, 3, 0, 7}
輸出 − 最大環形子陣列和為：22
解釋 − 給定陣列 {1, 2, 8, 4, 3, 0, 7}，其最大和子陣列為 7 + 1 + 2 + 8 + 4 = 22。
輸入 − int arr[] = { 2, 5, -1, 6, 9, 4, -5 }
輸出 − 最大環形子陣列和為：25
解釋 − 給定陣列 {2, 5, -1, 6, 9, 4, -5}，其最大和子陣列為 4 + 2 + 5 - 1 + 6 + 9 = 25。
下面程式中使用的方案如下：
輸入一個包含正負值的整數陣列。
計算陣列大小。
將陣列和大小傳遞給函式進行進一步處理。
建立一個臨時變數 total 並將其設定為 0
從 i = 0 開始迴圈到陣列大小
在迴圈內，將 total 設定為 total + arr[i]
設定 temp = arr[0], temp_2 = arr[0], temp_3 = arr[0], temp_4 = arr[0]
從 i = 1 開始迴圈到陣列大小
在迴圈內設定 temp = max(temp + arr[i], arr[i]), temp_2 = max(temp_2, temp), temp_3 = min(temp_3 + arr[i], arr[i]), temp_4 = min(temp_4, temp_3)
檢查 IF size == 1 則返回 arr[0]
檢查 IF temp_4 == total 則返回 temp_2
設定 max_sum = max(temp_3, total - temp_4)
返回 max_sum
列印結果。
示例
#include <bits/stdc++.h>
using namespace std;
int maximum(int arr[], int size){
int total = 0;
for (int i = 0; i < size; i++){
total += arr[i];
}
int temp = arr[0];
int temp_2 = arr[0];
int temp_3 = arr[0];
int temp_4 = arr[0];
for (int i = 1; i < size; i++){
temp = max(temp + arr[i], arr[i]);
temp_2 = max(temp_2, temp);
temp_3 = min(temp_3 + arr[i], arr[i]);
temp_4 = min(temp_4, temp_3);
}
if (size == 1){
return arr[0];
}
if (temp_4 == total){
return temp_2;
}
int max_sum = max(temp_3, total - temp_4);
return max_sum;
}
int main(){
int arr[] = { 2, 5, -1, 6, 9, 4, -5 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum circular subarray sum is: "<<maximum(arr, size) << endl;
return 0;
}輸出
如果執行以上程式碼，將生成以下輸出：
Maximum circular subarray sum is: 25
282 次檢視
