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

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

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

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

접두사 배열의 두 번째 요소 prefixArray[1] = prefixArray[0] + arr [1]

접두사 배열의 세 번째 요소 prefixArray[2] = prefixArray[1] + arr[2]

접두사 배열의 네 번째 요소 prefixArray[3] = prefixArray[2] + arr[3] . ..기타.

이 문제의 다양한 입력 및 출력 상황을 살펴보겠습니다. -

For int arr[] = {2, 4, 1, 5, 2}

출력 접두사 배열은 -2 2 3입니다. 8 10 접두사에 -1을 곱하여 배열의 합을 최대화합니다. 21

Explanation - 정수 배열이 있습니다. 먼저 배열의 접두사인 2를 얻고 여기에 -1을 곱합니다. 따라서 새 배열은 {-2, 4, 1, 5, 2}입니다. 이제 접두사 배열의 최대 합을 구성하겠습니다.

접두사 배열은 {-2, 2, 3, 8, 10}입니다. 마지막 단계는 합계를 -2+2+3+8+`0 = 21로 최대화하는 것입니다. 이는 최종 출력입니다.

In - int arr[] = {-1, 4, 2, 1, -9, 6};

출력 - 접두사 배열은 다음과 같습니다. 1 5 7 8 -1 5 -1을 곱한 배열, 최대화된 배열의 합은 다음과 같습니다. 19

Explanation- 정수 배열이 있습니다. 먼저 배열의 접두사 -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_array[size]를 선언합니다. 주어진 배열에 대한 접두사 배열을 생성하려면 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까지 반복을 시작합니다. 루프 내에서 prefix_array[i]를 prefix_array[i-1] + arr[i]로 설정합니다.

• 함수 내부에서 int maximum_sum(int prefix_array[], int size)

  • 임시 변수 temp를 선언하고 -1로 설정합니다.

  • 배열 크기가 나올 때까지 i부터 0까지 반복을 시작합니다. 루프 내에서 temp를 max(temp, prefix_array[i])

  • 배열 arr[temp +1]을 선언하고 배열의 모든 요소를 ​​0으로 초기화합니다.

  • 배열 크기가 나올 때까지 i부터 0까지 반복을 시작합니다. 루프 내에서 임시 변수 max_sum arr[prefix_array[i]]++

  • 을 선언하고 이를 0으로 설정합니다. i>0일 때 루프를 시작하려면 변수 i를 temp

  • 로 선언하세요. 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;
}

Output

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

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

위 내용은 C++에서는 접두사에 -1을 곱하여 배열의 합을 최대화합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!