ผลรวมของอาร์เรย์ย่อยสูงสุดโดยการพลิกสัญญาณขององค์ประกอบอาร์เรย์ K ส่วนใหญ่ใน C++

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

คำอธิบายโค้ด − ที่นี่ เราจะต้องหาองค์ประกอบสูงสุด k เพื่อพลิกอาร์เรย์ซึ่งจะทำให้ผลรวมของ subarray ที่สร้างจากอาร์เรย์นี้สูงสุด

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

ป้อนข้อมูล − array ={1, -2, 7, 0} k =2

ผลผลิต − 10

คำอธิบาย − เราจะพลิกเพียงองค์ประกอบเดียวคือ -2 มันทำให้ผลรวมอาร์เรย์ 10 ซึ่งเป็นค่าสูงสุดที่เป็นไปได้

เพื่อแก้ปัญหานี้ เราจะใช้วิธีการเขียนโปรแกรมแบบไดนามิก ซึ่งจะหาผลรวมสูงสุดของอาร์เรย์จาก i ^th ดัชนี j ^th จัดทำดัชนีและเก็บไว้ในอาร์เรย์ maxSumij[i][j] และพิจารณาทั้งสองกรณีหากองค์ประกอบพลิกหรือไม่มีองค์ประกอบพลิกกลับจะเป็นกรณีที่ดีที่สุด ซึ่งจะทำได้โดยใช้การเรียกซ้ำไปยังฟังก์ชัน ในท้ายที่สุด เราจะพบองค์ประกอบสูงสุดจากเมทริกซ์ maxSumij[i][j]

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include <bits/stdc++.h>
using namespace std;
#define right 2
#define left 4
int arraySumij[left][right];
int findSubarraySum(int i, int flips, int n, int a[], int k){
   if (flips > k)
      return -1e9;
   if (i == n)
      return 0;
   if (arraySumij[i][flips] != -1)
      return arraySumij[i][flips];
   int maxSum = 0;
   maxSum = max(0, a[i] + findSubarraySum(i + 1, flips, n, a, k));
   maxSum = max(maxSum, -a[i] + findSubarraySum(i + 1, flips + 1, n, a, k));
   arraySumij[i][flips] = maxSum;
   return maxSum;
}
int maxSubarraySumFlip(int a[], int n, int k){
   memset(arraySumij, -1, sizeof(arraySumij));
   int maxSum = -100;
   for (int i = 0; i < n; i++)
      maxSum = max(maxSum, findSubarraySum(i, 0, n, a, k));
   return maxSum;
}
int main() {
   int a[] = {-3, 56, -1, 8};
   int n = sizeof(a) / sizeof(a[0]);
   int k = 2;
   cout<<"Maximum subarry sum by fipping signs of at most "<<k<<" element is "<<maxSubarraySumFlip(a, n, k);
   return 0;
}

ผลลัพธ์

Maximum subarry sum by fipping signs of at most 2 element is 66