Dalam C++, maksimumkan jumlah tatasusunan dengan mendarab awalannya dengan -1

Kami mempunyai tatasusunan integer dan tugasnya ialah mendapatkan awalan tatasusunan dahulu dan kemudian darabkannya dengan -1, kedua hitung jumlah awalan tatasusunan dan akhirnya cari jumlah maksimum dalam awalan yang dijana tatasusunan.

Susun atur awalan dijana seperti berikut:

Unsur pertama tatasusunan awalan tatasusunan awalan[0] = elemen pertama tatasusunan

Unsur kedua tatasusunan awalanSusunatur[1] = tatasusunan awalan[0] + arr [1]

Elemen ketiga prefix array prefixArray[2] = prefixArray[1] + arr[2]

Elemen keempat prefix array prefixArray[3] = prefixArray[2] + arr[3] . ..dan lain-lain.

Mari kita lihat pelbagai situasi input dan output masalah ini -

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

Tatasusunan awalan output ialah: -2 2 3 8 10 Maksimumkan jumlah tatasusunan dengan mendarab awalannya dengan -1: 21

Penjelasan - Kami mempunyai tatasusunan integer. Mula-mula kita mendapat awalan tatasusunan, iaitu 2, dan darabkannya dengan -1. Jadi, tatasusunan baharu ialah {-2, 4, 1, 5, 2}. Sekarang, kita akan membentuk jumlah maksimum tatasusunan awalan.

Tatasusunan awalan ialah {-2, 2, 3, 8, 10}. Langkah terakhir ialah memaksimumkan jumlah kepada -2+2+3+8+`0 = 21, iaitu keluaran akhir.

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

Output - tatasusunan awalan ialah: 1 5 7 8 -1 5 Dengan menggabungkan awalan daripada tatasusunan dengan Didarab dengan -1, jumlah tatasusunan maksimum ialah: 19

Penjelasan- Kami mempunyai tatasusunan integer. Mula-mula kita ambil awalan tatasusunan sebagai -1 dan darabkannya dengan -1. Jadi, tatasusunan baharu ialah {1, 4, 2, 1, -9, 6}. Sekarang kita akan membentuk Tatasusunan awalan ialah {1, 5, 7, 8, -1, 5}. Langkah terakhir ialah memaksimumkan jumlah kepada 1+5+8+5 = 19, iaitu keluaran akhir.

Kaedah yang digunakan dalam atur cara di bawah adalah seperti berikut −

• Isytihar tatasusunan integer dan pembolehubah sementara x sebagai -1, dan kemudian tetapkan arr[0] kepada arr[0] * x.

• Kira saiz tatasusunan. Isytihar tatasusunan awalan awalan_susun[saiz]. Panggil fungsi create_prefix_arr(arr, size, prefix_array) untuk menjana tatasusunan awalan untuk tatasusunan yang diberikan. Mencetak tatasusunan awalan

• memanggil fungsi maximize_sum(prefix_array, size), yang akan menyimpan jumlah maksimum tatasusunan.

• Di dalam fungsi void create_prefix_arr(int arr[], saiz int, int prefix_array[])

  • set prefix_array[0] kepada arr[0].

  • Mulakan gelung dari i hingga 0 sehingga saiz tatasusunan. Di dalam gelung, tetapkan susunan_prefix[i] kepada tatasusunan_prefix[i-1] + arr[i].

• Di dalam fungsi int maximize_sum(int prefix_array[], saiz int)

  • isytiharkan temp pembolehubah sementara dan tetapkannya kepada -1.

  • Mulakan gelung dari i hingga 0 sehingga saiz tatasusunan. Di dalam gelung, tetapkan temp kepada max(temp, prefix_array[i])

  • Isytiharkan tatasusunan arr[temp +1] dan mulakan semua elemen tatasusunan kepada 0.

  • Mulakan gelung dari i hingga 0 sehingga saiz tatasusunan. Di dalam gelung, isytiharkan pembolehubah sementara max_sum arr[prefix_array[i]]++

  • dan tetapkannya kepada 0. Isytiharkan pembolehubah i sebagai temp

  • untuk memulakan gelung apabila i>0. Semak jika arr[i] > 0, kemudian tetapkan max_sum kepada max_sum + i, dan tetapkan arr[i-1]-- dan arr[i]--. Jika tidak, susutkan i sebanyak 1.

  • Pulangan max_sum.

Contoh

#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

Jika kita menjalankan kod di atas, output berikut akan dihasilkan

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

Atas ialah kandungan terperinci Dalam C++, maksimumkan jumlah tatasusunan dengan mendarab awalannya dengan -1. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!