C++의 최대 순환 하위 배열 합계

배열이 ​​주어지고 순환 방식의 하위 배열 합계가 최대값이 되도록 하위 배열을 형성하는 작업입니다.

입력 - 정수 arr[] ={1, 2, 8, 4, 3, 0, 7}

출력 − 최대 원형 하위 배열 합계는 − 22

설명 − {1, 2, 8, 4, 3, 0, 7}을 포함하는 배열이 주어지고 최대 합을 갖는 하위 배열은 7 + 1 + 2+ 8 + 4가 22가 됩니다.

입력 - 정수 arr[] ={ 2, 5, -1, 6, 9, 4, -5 }

출력 − 최대 원형 하위 배열 합계는 − 25

설명 − {2, 5, -1, 6, 9, 4, -5}를 포함하는 배열이 주어지고 최대 합을 갖는 하위 배열은 4 + 2 + 5 - 1 + 6 + 9가 25가 됩니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

• 양수 값과 음수 값을 모두 포함하는 정수 요소의 배열을 입력하십시오.

• 배열의 크기를 계산합니다.

• 추가 처리를 위해 배열과 크기를 함수에 전달합니다.

• 임시 변수를 총계로 만들고 0으로 설정

• 배열의 크기까지 i에서 0까지 FOR 루프 시작

• 루프 내에서 total + arr[i]

  로 합계를 설정합니다.

• 설정 온도 =arr[0], temp_2 =arr[0], temp_3 =arr[0], temp_4 =arr[0]

• 배열의 크기가 될 때까지 i에서 1까지 FOR 루프를 시작합니다.

• 루프 내에서 temp =max(temp + arr[i], arr[i]), temp_2 =max(temp_2, temp), temp_3 =min(temp_3 + arr[i], arr[i]), temp_4 =min (temp_4, temp_3)

• IF 크기 ==1을 확인한 다음 arr[0]

  을 반환합니다.

• IF temp_4 ==total을 확인한 다음 temp_2를 반환

• max_sum =max(temp_3, total - temp_4)

  설정

• max_sum 반환

• 결과를 인쇄하십시오.

예시

#include <bits/stdc++.h>
using namespace std;
int maximum(int arr[], int size){
   int total = 0;
   for (int i = 0; i < size; i++){
      total += arr[i];
   }
   int temp = arr[0];
   int temp_2 = arr[0];
   int temp_3 = arr[0];
   int temp_4 = arr[0];
   for (int i = 1; i < size; i++){
      temp = max(temp + arr[i], arr[i]);
      temp_2 = max(temp_2, temp);
      temp_3 = min(temp_3 + arr[i], arr[i]);
      temp_4 = min(temp_4, temp_3);
   }
   if (size == 1){
      return arr[0];
   }
   if (temp_4 == total){
      return temp_2;
   }
   int max_sum = max(temp_3, total - temp_4);
   return max_sum;
}
int main(){
   int arr[] = { 2, 5, -1, 6, 9, 4, -5 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum circular subarray sum is: "<<maximum(arr, size) << endl;
   return 0;
}

출력

위의 코드를 실행하면 다음 출력이 생성됩니다 -

Maximum circular subarray sum is: 25