Tối đa hóa tổng của mảng bằng cách nhân tiền tố của mảng với -1 trong C ++

Chúng ta được cung cấp một mảng số nguyên và nhiệm vụ trước tiên là tìm nạp tiền tố của một mảng rồi nhân nó với -1, thứ hai là tính tổng tiền tố của một mảng và cuối cùng tìm tổng lớn nhất từ mảng tiền tố được tạo.

Mảng tiền tố được tạo dưới dạng -

Phần tử đầu tiên của prefixArray [0] =phần tử đầu tiên của một mảng

Phần tử thứ hai của prefixArray [1] =prefixArray [0] + arr [1]

Phần tử thứ ba của prefixArray [2] =prefixArray [1] + arr [2]

Phần tử thứ tư của prefixArray [3] =prefixArray [2] + arr [3]… ..etc.

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}

Hết - Tiền tố mảng là:-2 2 3 8 10 Tối đa hóa tổng của mảng bằng cách nhân tiền tố của mảng với -1 là:21

Giải thích - chúng ta được cho với một mảng số nguyên. Vì vậy, trước tiên chúng ta sẽ tìm nạp tiền tố của một mảng là 2 và bội nó với -1. Vì vậy, mảng mới sẽ là {-2, 4, 1, 5, 2}. Bây giờ, chúng ta sẽ tạo mảng tiền tố là {-2, 2, 3, 8, 10}. Bước cuối cùng là tối đa hóa tổng là -2 + 2 + 3 + 8 + `0 =21 là kết quả cuối cùng.

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

Hết - Tiền tố mảng là:1 5 7 8 -1 5 Tối đa hóa tổng của mảng bằng cách nhân tiền tố của mảng với -1 là:19

Giải thích - chúng ta được cho với một mảng số nguyên. Vì vậy, trước tiên chúng ta sẽ tìm nạp tiền tố của một mảng là -1 và bội nó với -1. Vì vậy, mảng mới sẽ là {1, 4, 2, 1, -9, 6}. Bây giờ, chúng ta sẽ tạo mảng tiền tố là {1, 5, 7, 8, -1, 5}. Bước cuối cùng là tối đa hóa tổng là 1 + 5 + 8 + 5 =19, là kết quả cuối cùng.

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

Khai báo một mảng số nguyên và một biến tạm thời là x thành -1, sau đó đặt arr [0] thành arr [0] * x.
Tính kích thước của một mảng. Khai báo một mảng tiền tố là prefix_arry [size]. Gọi một hàm create_prefix_arr (arr, size, prefix_array) để tạo mảng tiền tố từ mảng đã cho. In mảng tiền tố
Gọi hàm Maximum_sum (prefix_array, size) sẽ lưu trữ tổng lớn nhất của mảng.
Bên trong hàm void create_prefix_arr (int arr [], int size, int prefix_array [])
- Đặt prefix_array [0] thành arr [0].
- 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 prefix_array [i] thành prefix_array [i-1] + arr [i].
Bên trong hàm int Maximum_sum (int prefix_array [], int size)
- Khai báo một biến tạm thời dưới dạng tạm thời và đặt nó thành -1.
- 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 độ là max (temp, prefix_array [i])
- Khai báo một mảng là arr [temp +1] và khởi tạo tất cả các phần tử của một mảng bằng 0.
- 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 arr [prefix_array [i]] ++
- Khai báo một biến tạm thời là max_sum và đặt nó thành 0. Khai báo một biến là int i thành temp
- Bắt đầu vòng lặp WHILE i> 0. Kiểm tra IF arr [i]> 0, sau đó đặt max_sum thành max_sum + i và giảm arr [i-1] - và giảm arr [i] -. ELSE, giảm i đi 1.
- Trả về max_sum.

Ví dụ

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

Đầu ra

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

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