Tối đa hóa tổng của mảng con sau khi nhân tất cả các phần tử của bất kỳ mảng con nào với X trong C ++

Chúng tôi được cung cấp với một mảng số nguyên và một biến số nguyên, tức là 'X'. Nhiệm vụ trước tiên là tạo mảng con từ mảng đã cho và sau đó nhân tất cả các phần tử của mảng con với một số nguyên X. Cuối cùng, hãy tìm ra các phần tử sẽ đóng góp tổng lớn nhất.

Hãy cho chúng tôi xem các tình huống đầu ra đầu vào khác nhau cho việc này -

Trong - int arr [] ={2, 4, 1, -5, -2}, X =3

Hết - Tối đa hóa tổng của mảng con sau khi nhân tất cả các phần tử của bất kỳ mảng con nào với X là:21

Giải thích - chúng ta được cung cấp với một mảng và một biến số nguyên là X. Đầu tiên, tìm nạp mảng con từ mảng đã cho, giả sử {2, 4, 1}. Bây giờ nhân tất cả các phần tử của một mảng con với X tức là 3 để mảng sẽ là {6, 12, 3, -5, -2}. Cuối cùng, hãy kiểm tra tổng của mảng con tối đa sẽ được trả về là 6 + 12 + 3 =21.

Trong - int arr [] ={-1, 2, -6, 3, -4}, x =-1

Hết - Tối đa hóa tổng của mảng con sau khi nhân tất cả các phần tử của bất kỳ mảng con nào với X là:11

Giải thích - chúng ta được cung cấp với một mảng và một biến số nguyên là X. Đầu tiên, tìm nạp mảng con từ mảng đã cho, giả sử {-1, -6, -4}. Bây giờ nhân tất cả các phần tử của một mảng con với X tức là -1 để mảng sẽ là {1, 2, 6, 3, 4}. Cuối cùng, hãy kiểm tra tổng của mảng con tối đa sẽ được trả về bằng 1 + 6 + 4 =11.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Nhập một mảng số nguyên và một biến số nguyên là 'X'. tính toán kích thước của một mảng và truyền dữ liệu vào hàm Max_Subarray (arr, size, x).
Bên trong hàm Max_Subarray (arr, size, x)
- Khai báo một mảng là int arr_2 [size] [3] và một biến tạm thời ở dạng tạm thời là 0.
- Khởi tạo tất cả các phần tử của mảng ‘arr_2’ với -1 bằng phương thức memset () trong C ++.
- Bắt đầu vòng lặp FOR từ i đến 0 cho đến hết kích thước của một mảng. Bên trong vòng lặp, đặt nhiệt độ cho lệnh gọi hàm max (tạm thời, kiểm tra (i, 0, arr, arr_2, size, x))
- Nhiệt độ trở lại.
Bên trong hàm int check (int first, int last, int arr [], int arr_2 [Max_size] [3], int size, int x)
- Khai báo một biến tạm thời là đếm đến 0.
- Kiểm tra IF đầu tiên =kích thước rồi trả về 0
- Kiểm tra IF arr_2 [first] [last]! =-1 rồi trả về arr_2 [first] [last].
- Kiểm tra IF last =0 sau đó gọi hàm max có sẵn của C ++ để tìm ra giá trị lớn nhất là max (count, arr [first] + check (first + 1, 0, arr, arr_2, size, x)) và cũng đặt số =max (count, x * arr [first] + check (first +1, 1, arr, arr_2, size, x))
- ELSE IF kiểm tra cuối cùng =1 sau đó đặt số đếm thành tối đa (đếm, x * arr [đầu tiên] + kiểm tra (đầu tiên + 1, 1, arr, arr_2, kích thước, x)) và đặt số lượng thành tối đa (đếm, arr [đầu tiên] + kiểm tra (đầu tiên + 1, 2, arr, arr_2, kích thước, x))
- ELSE, đặt số đếm thành tối đa (count, arr [first] + check (first + 1, 2, arr, arr_2, size, x));
- Trả lại arr_2 [đầu tiên] [cuối cùng] để đếm.
In kết quả.

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau

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