C++ 최대 하위 배열 합계 O(n^2) 시간을 찾는 프로그램(순진한 방법)

우리는 최대 부분배열 합 O(n^2) 시간(순진한 방법)을 찾는 C++ 프로그램을 개발할 것입니다.

알고리즘

Begin
   Take the array elements as input.
   Make a loop for the length of the sub-array from 1 to n, within this loop,
   Make another loop nested with the previous one, calculate the sum of first sub-array of that length.
   For remaining sub-array sum, add the next element to the sum and subtract the first element of that sub-array.
   Compare it with the global max and update if found out to be more.
   Print the max sub-array and their sum as a result.
End.

예시 코드

#include<iostream>
using namespace std;
int main() {
   int n, i, j, m=-1, s, ini_m, fi_m;
   cout<<"\nEnter the number of data element in the array: ";
   cin>>n;
   int a[n];
   for(i = 0; i < n; i++) {
      cout<<"Enter element "<<i+1<<": ";
      cin>>a[i];
   }
   for(i = 1; i < n+1; i++) {
      s = 0;
      for(j = 0; j < n; j++) {
         if(j < i)
            s += a[j];
         else
            s = s+a[j]-a[j-i];
         if(m< s) {
            ini_m = j-i+1;
            fi_m = j;
            m = s;
         }
      }
   }
   cout<<"\nThe maximum sub array is: ";
   for(i = ini_m; i <= fi_m; i++)
      cout<<a[i]<<" ";
      cout<<"\nThe maximum sub-array sum is: "<<m;
}

출력

Enter the number of data element in the array: 10
Enter element 1: 1
Enter element 2: -2
Enter element 3: 3
Enter element 4: -4
Enter element 5: 5
Enter element 6: -6
Enter element 7: 7
Enter element 8: 8
Enter element 9: -9
Enter element 10: 10
The maximum sub array is: 7 8 -9 10
The maximum sub-array sum is: 16