資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++程式中重複連線後建立的陣列中的最大子陣列和
在這個問題中，我們得到一個大小為n的陣列arr[]和一個整數k。我們的任務是建立一個程式，在重複連線後的陣列中找到最大子陣列和。
問題描述 − 我們將找到從重複連線arr k次的陣列中取出的子陣列的最大和。
示例
讓我們舉個例子來理解這個問題。
輸入
arr[] = {−9, −5, 14, 6} k = 2輸出
26
解釋
New array after repeating : {−9, −5, 14, 6, −9, −5, 14, 6}
Subarray with maximum sum = {14, 6, −9, −5, 14, 6}
Sum = 26解決方案方法
一個簡單的解決方案是建立一個新的陣列，該陣列在將arr[]連線k次後形成，然後找到具有最大和的子陣列。為此，最好的方法是使用Kadane演算法。
示例
演示我們解決方案工作的程式：
#include <iostream>
using namespace std;
int calcMaxSubArraySum(int arr[], int n, int k){
int newArr[2*n];
for(int i = 0; i < k*n; i++)
newArr[i] = arr[i%n];
int maxSum = −1000, sum = 0;
for (int i = 0; i < k*n; i++) {
sum = sum + newArr[i];
if (maxSum < sum)
maxSum = sum;
if (sum < 0)
sum = 0;
}
return maxSum;
}
int main(){
int arr[] = { −9, −5, 14, 6 };
int k = 2;
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum subarray sum in an array created after repeated concatenation is "<<calcMaxSubArraySum(arr, n, k);
return 0;
}輸出
The maximum subarray sum in an array created after repeated concatenation is 26
這種方法很好，但可以使用更有效的模算術方法來解決問題。
模算術是指我們使用模運算子來獲取方程的餘數。
為了解決這個問題，我們將使用模算術而不是透過重複連線來建立陣列。其餘解決方案保持不變。
示例
演示我們解決方案工作的程式：
#include <iostream>
using namespace std;
int calcMaxSubArraySum(int arr[], int n, int k){
int maxSum = −1000, sum = 0;
for (int i = 0; i < k*n; i++) {
sum = sum + arr[i%n];
if (maxSum < sum)
maxSum = sum;
if (sum < 0)
sum = 0;
}
return maxSum;
}
int main(){
int arr[] = { −9, −5, 14, 6 };
int k = 2;
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum subarray sum in an array created after
repeated concatenation is "<<calcMaxSubArraySum(arr, n, k);
return 0;
}輸出
The maximum subarray sum in an array created after repeated concatenation is 26
更新於：2020年12月9日
144 次瀏覽
廣告