เพิ่มผลรวมของอาร์เรย์ให้มากที่สุดโดยการคูณส่วนนำหน้าของอาร์เรย์ด้วย -1 ใน C++

เราได้รับอาร์เรย์จำนวนเต็มและภารกิจคือการดึงคำนำหน้าของอาร์เรย์ก่อนแล้วจึงคูณด้วย -1 คำนวณผลรวมคำนำหน้าของอาร์เรย์เป็นลำดับที่สอง และสุดท้ายหาผลรวมสูงสุดจากอาร์เรย์คำนำหน้าที่สร้างขึ้น

อาร์เรย์คำนำหน้าถูกสร้างขึ้นเป็น −

องค์ประกอบแรกของ prefixArray[0] =องค์ประกอบแรกของอาร์เรย์

องค์ประกอบที่สองของ prefixArray[1] =prefixArray[0] + arr[1]

องค์ประกอบที่สามของ prefixArray[2] =prefixArray[1] + arr[2]

องค์ประกอบที่สี่ของ prefixArray[3] =prefixArray[2] + arr[3] …..เป็นต้น

ให้เราดูสถานการณ์อินพุตเอาต์พุตต่างๆ สำหรับสิ่งนี้ -

ใน − int arr[] ={2, 4, 1, 5, 2}

ออก − Prefix array is:-2 2 3 8 10 เพิ่มผลรวมของ array สูงสุดโดยการคูณ prefix ของอาร์เรย์ด้วย -1 คือ:21

คำอธิบาย − เราได้รับอาร์เรย์จำนวนเต็ม ดังนั้นก่อนอื่นเราจะดึงคำนำหน้าของอาร์เรย์ที่เป็น 2 และคูณด้วย -1 ดังนั้นอาร์เรย์ใหม่จะเป็น {-2, 4, 1, 5, 2} ตอนนี้เราจะสร้างอาร์เรย์คำนำหน้าซึ่งก็คือ {-2, 2, 3, 8, 10} ขั้นตอนสุดท้ายคือการเพิ่มผลรวมสูงสุดเป็น -2+2+3+8+`0 =21 ซึ่งเป็นผลลัพธ์สุดท้าย

ใน − int arr[] ={-1, 4, 2, 1, -9, 6};

ออก − Prefix array คือ:1 5 7 8 -1 5 เพิ่มผลรวมของอาร์เรย์ให้มากที่สุดโดยการคูณส่วนนำหน้าของอาร์เรย์ด้วย -1 คือ 19

คำอธิบาย − เราได้รับอาร์เรย์จำนวนเต็ม ดังนั้นก่อนอื่นเราจะดึงคำนำหน้าของอาร์เรย์ซึ่งก็คือ -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_arry[ขนาด] เรียกใช้ฟังก์ชัน 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].

  • เริ่มลูป FOR จาก i ถึง 0 จนถึงขนาดของอาร์เรย์ ภายในลูป ให้ตั้งค่า prefix_array[i] เป็น prefix_array[i-1] + arr[i]

• ภายในฟังก์ชัน int maximum_sum(int prefix_array[], int size)

  • ประกาศตัวแปรชั่วคราวเป็น temp และตั้งค่าเป็น -1

  • เริ่มลูป FOR จาก i ถึง 0 จนถึงขนาดของอาร์เรย์ ภายในลูป ตั้งค่า temp เป็น max(temp, prefix_array[i])

  • ประกาศอาร์เรย์เป็น arr[temp +1] และกำหนดค่าเริ่มต้นองค์ประกอบทั้งหมดของอาร์เรย์ด้วย 0

  • เริ่มลูป FOR จาก i ถึง 0 จนถึงขนาดของอาร์เรย์ ภายในลูป ให้ตั้งค่า arr[prefix_array[i]]++

  • ประกาศตัวแปรชั่วคราวเป็น max_sum และตั้งค่าเป็น 0 ประกาศตัวแปรเป็น int i ถึง temp

  • เริ่มวนซ้ำในขณะที่ i>0 ตรวจสอบ IF arr[i]> 0 จากนั้นตั้งค่า max_sum เป็น max_sum + i และลดค่า arr[i-1]-- และลดค่า arr[i]-- ELSE ลดค่า 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;
}

ผลลัพธ์

หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้

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