ผลรวมของ subarray แบบวงกลมสูงสุดใน C++

เราได้รับอาร์เรย์และภารกิจคือการสร้างอาร์เรย์ย่อยเพื่อให้ผลรวมของอาร์เรย์ย่อยในรูปแบบวงกลมได้ผลลัพธ์เป็นค่าสูงสุด

ป้อนข้อมูล − int arr[] ={1, 2, 8, 4, 3, 0, 7}

ผลผลิต − ผลรวม subarray แบบวงกลมสูงสุดคือ − 22

คำอธิบาย − เราได้รับอาร์เรย์ที่มี {1, 2, 8, 4, 3, 0, 7} และอาร์เรย์ย่อยของอาร์เรย์ที่มีผลรวมสูงสุดจะเป็น 7 + 1 + 2+ 8 + 4 คือ 22

ป้อนข้อมูล − int arr[] ={ 2, 5, -1, 6, 9, 4, -5 }

ผลผลิต − ผลรวม subarray แบบวงกลมสูงสุดคือ − 25

คำอธิบาย − เราได้รับอาร์เรย์ที่มี {2, 5, -1, 6, 9, 4, -5} และอาร์เรย์ย่อยของอาร์เรย์ที่มีผลรวมสูงสุดจะเป็น 4 + 2 + 5 - 1 + 6 + 9 คือ 25

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• ป้อนอาร์เรย์ขององค์ประกอบจำนวนเต็มที่มีทั้งค่าบวกและค่าลบ

• คำนวณขนาดของอาร์เรย์

• ส่งอาร์เรย์และขนาดไปยังฟังก์ชันเพื่อการประมวลผลต่อไป

• สร้างตัวแปรชั่วคราวเป็นผลรวมและตั้งค่าเป็น 0

• เริ่มการวนซ้ำ FOR จาก i ถึง 0 จนถึงขนาดของอาร์เรย์

• ภายในลูป ตั้งค่าผลรวมด้วยผลรวม + arr[i]

• ตั้งค่า temp =arr[0], temp_2 =arr[0], temp_3 =arr[0], temp_4 =arr[0]

• เริ่มลูป FOR จาก i ถึง 1 จนถึงขนาดของอาร์เรย์

• ภายในลูป set temp =max(temp + arr[i], arr[i]), temp_2 =max(temp_2, temp), temp_3 =min(temp_3 + arr[i], arr[i]), temp_4 =min (temp_4, temp_3)

• ตรวจสอบขนาด IF ==1 แล้วส่งคืน arr[0]

• ตรวจสอบ IF temp_4 ==total แล้วคืนค่า temp_2

• ตั้งค่า max_sum =max(temp_3, Total - temp_4)

• ส่งคืน max_sum

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int maximum(int arr[], int size){
   int total = 0;
   for (int i = 0; i < size; i++){
      total += arr[i];
   }
   int temp = arr[0];
   int temp_2 = arr[0];
   int temp_3 = arr[0];
   int temp_4 = arr[0];
   for (int i = 1; i < size; i++){
      temp = max(temp + arr[i], arr[i]);
      temp_2 = max(temp_2, temp);
      temp_3 = min(temp_3 + arr[i], arr[i]);
      temp_4 = min(temp_4, temp_3);
   }
   if (size == 1){
      return arr[0];
   }
   if (temp_4 == total){
      return temp_2;
   }
   int max_sum = max(temp_3, total - temp_4);
   return max_sum;
}
int main(){
   int arr[] = { 2, 5, -1, 6, 9, 4, -5 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum circular subarray sum is: "<<maximum(arr, size) << endl;
   return 0;
}

ผลลัพธ์

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

Maximum circular subarray sum is: 25