เพิ่มผลรวมของ subarray ให้สูงสุดหลังจากคูณองค์ประกอบทั้งหมดของ subarray ด้วย X ใน C++

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

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

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

ออก − เพิ่มผลรวมของ subarray สูงสุดหลังจากคูณองค์ประกอบทั้งหมดของ subarray ใดๆ ด้วย X คือ:21

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

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

ออก − เพิ่มผลรวมของ subarray สูงสุดหลังจากคูณองค์ประกอบทั้งหมดของ subarray ใดๆ ด้วย X คือ:11

คำอธิบาย − เราได้รับอาร์เรย์และตัวแปรจำนวนเต็มเป็น X ขั้นแรก ดึงข้อมูลอาร์เรย์ย่อยจากอาร์เรย์ที่กำหนด สมมติว่า {-1, -6, -4} ตอนนี้คูณองค์ประกอบทั้งหมดของ subarray ด้วย 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[ขนาด][3] และตัวแปรชั่วคราวเป็น temp ถึง 0

  • เริ่มต้นองค์ประกอบทั้งหมดของอาร์เรย์ 'arr_2' ด้วย -1 โดยใช้วิธี memset() ใน C++

  • เริ่มลูป FOR จาก i ถึง 0 จนถึงขนาดของอาร์เรย์ ภายในลูป ให้ตั้งค่า temp เป็นการเรียกใช้ฟังก์ชัน max(temp, check(i, 0, arr, arr_2, size, x))

  • อุณหภูมิขากลับ

• ภายในฟังก์ชัน int check(int first, int last, int arr[], int arr_2[Max_size][3], int size, int x)

  • ประกาศตัวแปรชั่วคราวนับเป็น 0

  • ตรวจสอบว่า IF first =size แล้วคืนค่า 0

  • ตรวจสอบ IF arr_2[first][last] !=-1 แล้ว return arr_2[first][last].

  • ตรวจสอบว่า IF สุดท้าย =0 จากนั้นเรียกใช้ฟังก์ชัน inbuilt max ของ C++ เพื่อค้นหาค่าสูงสุดเป็น max(count, arr[first] + check(first + 1, 0, arr, arr_2, size, x)) และตั้งค่าการนับ =max(นับ, x * arr[ก่อน] + ตรวจสอบ (ก่อน + 1, 1, arr, arr_2, ขนาด, x))

  • มิฉะนั้น IF ตรวจสอบครั้งสุดท้าย =1 จากนั้นตั้งค่าการนับเป็นสูงสุด (นับ x * arr[ก่อน] + ตรวจสอบ (แรก + 1, 1, arr, arr_2, ขนาด, x)) และตั้งค่าให้สูงสุด (นับ, arr[ก่อน] + ตรวจสอบ (ก่อน + 1, 2, arr, arr_2, ขนาด, x))

  • ELSE ตั้งค่าการนับเป็น max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x));

  • กลับ arr_2[first][last] เพื่อนับ

• พิมพ์ผลลัพธ์

ตัวอย่าง

#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