ในปัญหานี้ เราได้รับอาร์เรย์และตัวเลข k งานของเราคือสร้างโปรแกรมที่จะหาผลรวมของ subarray สูงสุดในอาร์เรย์ที่เกิดขึ้นจากการทำซ้ำอาร์เรย์ k เวลาใน c++
คำอธิบายปัญหา − ที่นี่ เราจะพบผลรวมสูงสุดของอาร์เรย์ย่อยที่เกิดขึ้นจากอาร์เรย์ที่เกิดขึ้นจากการทำซ้ำอาร์เรย์ที่กำหนด 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 คูณ ซึ่งให้ผลรวมตามจริง
หากผลรวม <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
