Subarray Sum สูงสุดหลังจากกลับองค์ประกอบสูงสุดสององค์ประกอบใน C++

ในปัญหานี้เราได้รับอาร์เรย์ งานของเราคือสร้างโปรแกรมที่จะหาผลรวมของ subarray สูงสุดหลังจากกลับองค์ประกอบไม่เกินสององค์ประกอบใน C++

คำอธิบายปัญหา − ในที่นี้ เราสามารถต้องหาอาร์เรย์ย่อยที่จะให้ผลรวมสูงสุดในการกลับเครื่องหมายของตัวเลขสองตัวใดๆ ของอาร์เรย์

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล − array ={-5, 1, 3, 8, -2, 4, 7}

ผลผลิต − 30

คำอธิบาย − เราจะพิจารณาองค์ประกอบจากดัชนี 0 ถึง 6 และกลับค่า -5 และ -2 เพื่อให้ได้อาร์เรย์ที่มีผลรวมสูงสุด

เพื่อแก้ปัญหานี้ เราจะใช้วิธีการเขียนโปรแกรมแบบไดนามิก เราจะตรวจสอบผลรวมสูงสุดของอาร์เรย์ย่อยทั้งหมดที่มีขนาด 1 ถึง n (ความยาวของอาร์เรย์) ดังนั้น สำหรับแต่ละ subarray เรามีสามกรณี -

กรณีที่1 − ผลรวมสูงสุดของอาร์เรย์ย่อยหลังจากสลับสององค์ประกอบของอาร์เรย์ย่อย

กรณีที่2 − ผลรวมสูงสุดของอาร์เรย์ย่อยหลังจากกลับองค์ประกอบหนึ่งของอาร์เรย์ย่อย

กรณีที่3 − ผลรวมสูงสุดของอาร์เรย์ย่อยหลังจากการกลับองค์ประกอบศูนย์ของอาร์เรย์ย่อย

ดังนั้น ทุกครั้งที่เรามีการวนซ้ำ เราจะค้นหาค่าสูงสุดของอาร์เรย์ และองค์ประกอบปัจจุบันและกำหนดค่าค่าสูงสุดของอาร์เรย์นั้น

เราจะเก็บผลรวมสูงสุดไว้ในอาร์เรย์ 2 มิติชื่อ maxSum และผลรวมสูงสุดสุดท้ายคือองค์ประกอบสูงสุดของอาร์เรย์ 2 มิติ

ตัวอย่าง

โปรแกรมแสดงการใช้งานโซลูชันของเรา

#include <bits/stdc++.h>
using namespace std;
int findMaxSubarraySum(int a[], int n) {
   int maxSubarraySum = 0;
   int* arr = new int[n + 1];
   for (int i = 1; i <= n; i++)
      arr[i] = a[i - 1];
   int** maxSum = new int*[n + 1];
   for (int i = 0; i <= n; i++)
      maxSum[i] = new int[3];
   for (int i = 1; i <= n; ++i) {
      maxSum[i][0] = max(arr[i], maxSum[i - 1][0] + arr[i]);
      maxSum[i][1] = max(0, maxSum[i - 1][0]) - arr[i];
      if (i >= 2)
      maxSum[i][1] = max(maxSum[i][1], maxSum[i - 1][1] + arr[i]);
      if (i >= 2)
         maxSum[i][2] = maxSum[i - 1][1] - arr[i];
      if (i >= 3)
         maxSum[i][2] = max(maxSum[i][2], maxSum[i - 1][2] + arr[i]);
      maxSubarraySum = max(maxSubarraySum, maxSum[i][0]);
      maxSubarraySum = max(maxSubarraySum, maxSum[i][1]);
      maxSubarraySum = max(maxSubarraySum, maxSum[i][2]);
   }
   return maxSubarraySum;
}
int main(){
   int arr[] = {-5, 1, 3, 8, -2, 4, 7};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum subarray sum after inverting at most two elements is "<<findMaxSubarraySum(arr, n);
   return 0;
}

ผลลัพธ์

Maximum subarray sum after inverting at most two elements is 30