資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中重複給定陣列 k 次形成的陣列中的最大子陣列和
在這個問題中，我們給定一個數組和一個數字 k。我們的任務是建立一個程式，該程式將在 C++ 中找到由重複給定陣列 k 次形成的陣列中的最大子陣列和。
問題描述 - 在這裡，我們將找到由重複給定陣列 k 次形成的陣列中形成的子陣列的最大和。
讓我們舉個例子來理解這個問題，
輸入 - 陣列 = {3, 5, 1} k = 2
輸出 - 18
解釋 -
array formed by repeating k times,
array = {3, 5, 1, 3, 5, 1}
Maximum subarray sum = 3+5+1+3+5+1 = 18為了解決這個問題，我們將計算陣列所有元素的總和。
然後根據總和，我們將計算子陣列和計算。
如果 sum > 0，我們將把陣列的和乘以 k 次，這給出了實際的和。
如果 sum < 0，我們將找到具有 maxSum 的子陣列，取兩次陣列重複。
示例
程式顯示我們解決方案的實現，
#include<iostream>
using namespace std;
void repeatArray(int *arr, int *b, int k,int len) {
int j = 0;
while (k > 0){
for (int i = 0; i < len; i++)
b[j++] = arr[i];
k--;
}
}
long subArraySum(int *a,int len) {
int max = 0;
long newmax = 0;
for (int i = 0; i < len; i++) {
newmax = newmax + a[i];
if (max < newmax)
max = newmax;
if (newmax < 0)
newmax = 0;
}
return max;
}
long findMaxSubArraySum(int *arr, int k,int len) {
int arraySum = 0;
long maxSum = 0;
int b[(2 * len)]= {0};
repeatArray(arr, b, 2,len);
for (int i = 0; i < len; i++)
arraySum += arr[i];
maxSum = subArraySum(b,2*len);
if (arraySum > 0)
maxSum = subArraySum(b,2*len) + (k - 2) * arraySum;
return maxSum;
}
int main() {
int arr[] = { 3, 5, 1};
int length=sizeof(arr)/sizeof(arr[0]);
int k = 3;
cout<<"The maximum subarray sum in array formed by repeating the given array "<<k<<" times is "<<findMaxSubArraySum(arr, k,length);
return 0;
}輸出
The maximum subarray sum in array formed by repeating the given array 3 times is 27
更新於: 2020年6月3日
161 次檢視
廣告