이 튜토리얼에서는 반복 연결 후 생성된 배열에서 최대 하위 배열 합계를 찾는 프로그램에 대해 설명합니다.
이를 위해 배열과 정수 K가 제공됩니다. 우리의 임무는 주어진 배열이 K번 반복될 때 최대 요소를 가진 하위 배열을 찾는 것입니다.
예시
#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; }
출력
Maximum contiguous sum is 30