C++에서 하위 배열의 모든 요소에 X를 곱한 후 하위 배열 합계를 최대화합니다.

<시간/>

정수 배열과 정수 변수, 즉 'X'가 주어집니다. 작업은 먼저 주어진 배열에서 하위 배열을 구성한 다음 하위 배열의 모든 요소에 정수 X를 곱하는 것입니다. 마지막으로 최대 합계에 기여할 요소를 찾습니다.

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

안 - 정수 arr[] ={2, 4, 1, -5, -2}, X =3

밖으로 − 하위 배열의 모든 요소에 X를 곱한 후 하위 배열 합계를 최대화합니다. 21

설명 - 배열과 정수 변수가 X로 주어집니다. 먼저, {2, 4, 1}이라고 가정해 봅시다. 이제 하위 배열의 모든 요소에 X 즉 3을 곱하면 배열이 {6, 12, 3, -5, -2}가 됩니다. 마지막으로 6 + 12 + 3 =21이 반환될 최대 하위 배열 합계를 확인합니다.

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

밖 − 하위 배열의 모든 요소에 X를 곱한 후 하위 배열 합계를 최대화합니다. 11

설명 - 배열과 정수 변수가 X로 주어집니다. 먼저, {-1, -6, -4}라고 가정해 봅시다. 이제 하위 배열의 모든 요소에 X 즉 -1을 곱하면 배열이 {1, 2, 6, 3, 4}가 됩니다. 마지막으로 1 + 6 + 4 =11이 반환될 최대 하위 배열 합계를 확인합니다.

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

정수 배열과 정수 변수를 'X'로 입력합니다. 배열의 크기를 계산하고 Max_Subarray(arr, size, x) 함수에 데이터를 전달합니다.
Max_Subarray(arr, size, x)
함수 내부
- 배열을 int arr_2[size][3]으로 선언하고 임시 변수를 temp로 0으로 선언합니다.
- C++에서 memset() 메서드를 사용하여 배열 'arr_2'의 모든 요소를 -1로 초기화합니다.
- 배열의 크기까지 i에서 0까지 루프 FOR를 시작합니다. 루프 내에서 max(temp, check(i, 0, arr, arr_2, size, x))
  함수 호출로 temp를 설정합니다.
- 반환 온도.
함수 내부 int check(int first, int last, int arr[], int arr_2[Max_size][3], int size, int x)
- 임시 변수를 count로 0으로 선언합니다.
- 먼저 IF =크기를 확인한 다음 0을 반환합니다.
- IF arr_2[first][last] !=-1을 확인한 다음 arr_2[first][last]를 반환합니다.
- IF last =0인지 확인한 다음 C++의 내장 max 함수를 호출하여 최대값을 max(count, arr[first] + check(first + 1, 0, arr, arr_2, size, x))로 찾고 count도 설정합니다. =max(count, x * arr[첫 번째] + check(첫 번째 + 1, 1, arr, arr_2, 크기, x))
- ELSE IF check last =1 다음 count를 max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x))로 설정하고 count를 max(count, arr[first]로 설정합니다. + 확인(첫 번째 + 1, 2, arr, arr_2, 크기, x))
- ELSE, count를 max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x))로 설정;
- 계산하려면 rr_2[첫 번째][마지막]을 반환합니다.
결과를 인쇄하십시오.

예

#include <bits/stdc++.h>
using namespace std;
#define Max_size 5

int check(int first, int last, int arr[], int arr_2[Max_size][3], int size, int x){
   int count = 0;
      if(first == size){
         return 0;
      }
      if(arr_2[first][last] != -1){
         return arr_2[first][last];}
      if (last == 0){
         count = max(count, arr[first] + check(first + 1, 0, arr, arr_2, size, x));
         count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x));
      }
      else if(last == 1){
         count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x));
         count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x));
      }
      else{
         count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x));
      }
      return arr_2[first][last] = count;
}
int Max_Subarray(int arr[], int size, int x){
   int arr_2[size][3];
   int temp = 0;
   memset(arr_2, -1, sizeof arr_2);
   for(int i = 0; i < size; i++){
      temp = max(temp, check(i, 0, arr, arr_2, size, x));
   }
   return temp;
}
int main(){
   int arr[] = {2, 4, 1, -5, -2};
   int size = sizeof(arr) / sizeof(arr[0]);
   int x = 3;
   cout<<"Maximize the subarray sum after multiplying all elements of any subarray with X are: "<<Max_Subarray(arr, size, x);
   return 0;
}

출력

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

Maximize the subarray sum after multiplying all elements of any subarray with X are: 21