C++에서 배열의 접두사에 -1을 곱하여 배열의 합을 최대화합니다.

<시간/>

정수 배열이 주어지고 작업은 먼저 배열의 접두사를 가져온 다음 -1을 곱하고, 두 번째로 배열의 접두사 합을 계산하고 마지막으로 생성된 접두사 배열에서 최대 합을 찾는 것입니다.

접두사 배열은 다음과 같이 생성됩니다. -

prefixArray[0]의 첫 번째 요소 =배열의 첫 번째 요소

prefixArray[1]의 두 번째 요소 =prefixArray[0] + arr[1]

prefixArray[2]의 세 번째 요소 =prefixArray[1] + arr[2]

prefixArray[3]의 네 번째 요소 =prefixArray[2] + arr[3] …..etc.

이에 대한 다양한 입력 출력 시나리오를 살펴보겠습니다. -

에서 - 정수 arr[] ={2, 4, 1, 5, 2}

밖으로 − 접두사 배열:-2 2 3 8 10 배열의 접두사에 -1을 곱하여 배열의 합을 최대화:21

설명 - 정수 배열이 주어집니다. 따라서 먼저 2인 배열의 접두사를 가져와 -1로 곱합니다. 따라서 새 배열은 {-2, 4, 1, 5, 2}가 됩니다. 이제 {-2, 2, 3, 8, 10}인 접두사 배열을 형성합니다. 마지막 단계는 최종 출력인 -2+2+3+8+`0 =21로 합을 최대화하는 것입니다.

에서 - 정수 arr[] ={-1, 4, 2, 1, -9, 6};

밖으로 − 접두사 배열:1 5 7 8 -1 5 배열의 접두사에 -1을 곱하여 배열의 합을 최대화:19

설명 - 정수 배열이 주어집니다. 따라서 먼저 -1인 배열의 접두사를 가져오고 -1을 곱합니다. 따라서 새 배열은 {1, 4, 2, 1, -9, 6}이 됩니다. 이제 {1, 5, 7, 8, -1, 5}인 접두어 배열을 형성합니다. 마지막 단계는 최종 출력인 1+5+8+5 =19로 합을 최대화하는 것입니다.

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

정수 배열과 임시 변수를 x에서 -1로 선언한 다음 arr[0]을 arr[0] * x로 설정합니다.
배열의 크기를 계산합니다. 접두사 배열을 prefix_arry[크기]로 선언합니다. create_prefix_arr(arr, size, prefix_array) 함수를 호출하여 주어진 배열에서 접두사 배열을 생성합니다. 접두어 배열 인쇄
배열의 최대 합을 저장할 maximum_sum(prefix_array, size) 함수를 호출합니다.
함수 내부에서 void create_prefix_arr(int arr[], int size, int prefix_array[])
- prefix_array[0]을(를) arr[0]으로 설정합니다.
- 배열의 크기까지 i에서 0까지 루프 FOR를 시작합니다. 루프 내에서 prefix_array[i]를 prefix_array[i-1] + arr[i]로 설정합니다.
함수 내부 int maximum_sum(int prefix_array[], int size)
- 임시 변수를 temp로 선언하고 -1로 설정합니다.
- 배열의 크기까지 i에서 0까지 루프 FOR를 시작합니다. 루프 내에서 temp를 max(temp, prefix_array[i])
  로 설정합니다.
- 배열을 arr[temp +1]로 선언하고 배열의 모든 요소를 0으로 초기화합니다.
- 배열의 크기까지 i에서 0까지 루프 FOR를 시작합니다. 루프 내에서 arr[prefix_array[i]]++
  를 설정합니다.
- 임시 변수를 max_sum으로 선언하고 0으로 설정합니다. 변수를 int i로 선언하여 temp
- 루프 WHILE i>0을 시작합니다. IF arr[i]> 0을 확인한 다음 max_sum을 max_sum + i로 설정하고 arr[i-1]--을 감소시키고 arr[i]--를 감소시킵니다. 그렇지 않으면 i를 1만큼 감소시킵니다.
- max_sum을 반환합니다.

예시

#include <bits/stdc++.h>
using namespace std;
#define Max_size 5
//create the prefix array
void create_prefix_arr(int arr[], int size, int prefix_array[]) {
   prefix_array[0] = arr[0];
   for(int i=0; i<size; i++)  {
      prefix_array[i] = prefix_array[i-1] + arr[i];
   }
}
//find the maximum sum of prefix array
int maximize_sum(int prefix_array[], int size) {
   int temp = -1;
   for(int i = 0; i < size; i++) {
      temp = max(temp, prefix_array[i]);
   }
   int arr[temp + 1];
   memset(arr, 0, sizeof(arr));

   for(int i = 0; i < size; i++) {
      arr[prefix_array[i]]++;
   }
   int max_sum = 0;
   int i = temp;
   while(i>0) {
      if(arr[i] > 0) {
         max_sum = max_sum + i;
         arr[i-1]--;
         arr[i]--;
      } else {
         i--;
      }
   }
   return max_sum;
}

int main() {
   int arr[] = {2, 4, 1, 5, 2};
      int x = -1;
      arr[0] = arr[0] * x;
      int size = sizeof(arr) / sizeof(arr[0]);
   int prefix_array[size];

   //call function to create a prefix array
   create_prefix_arr(arr, size, prefix_array);
   //print the prefix array
   cout<<"Prefix array is: ";
   for(int i = 0; i < size; i++) {
      cout << prefix_array[i] << " ";
   }
   //print the maximum sum of prefix array
   cout<<"\nMaximize the sum of array by multiplying prefix of array with -1 are:" <<maximize_sum(prefix_array, size);
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Prefix array is: -2 2 3 8 10
Maximize the sum of array by multiplying prefix of array with -1 are: 21