Tổng mảng con tối đa trong một mảng được tạo sau khi nối lặp lại trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm tổng của mảng con tối đa trong một mảng được tạo sau khi nối lặp lại.

Đối với điều này, chúng ta sẽ được cung cấp một mảng và một số nguyên K. Nhiệm vụ của chúng ta là tìm mảng con có số phần tử lớn nhất khi mảng đã cho được lặp lại K lần.

Ví dụ

#include<bits/stdc++.h>
using namespace std;
//returning sum of maximum subarray
int maxSubArraySumRepeated(int a[], int n, int k) {
   int max_so_far = INT_MIN, max_ending_here = 0;
   for (int i = 0; i < n*k; i++) {
      max_ending_here = max_ending_here + a[i%n];
      if (max_so_far < max_ending_here)
      max_so_far = max_ending_here;
      if (max_ending_here < 0) max_ending_here = 0;
   }
   return max_so_far;
}
int main() {
   int a[] = {10, 20, -30, -1};
   int n = sizeof(a)/sizeof(a[0]);
   int k = 3;
   cout << "Maximum contiguous sum is "
   << maxSubArraySumRepeated(a, n, k);
   return 0;
}

Đầu ra

Maximum contiguous sum is 30