ผลรวม subarray สูงสุดลบอย่างน้อยหนึ่งองค์ประกอบใน C++

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

โดยพื้นฐานแล้ว เราจำเป็นต้องหาองค์ประกอบหนึ่งซึ่งเมื่อนำออกแล้วจะให้ผลรวมสูงสุดสำหรับองค์ประกอบที่เหลืออยู่ในอาร์เรย์

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

ป้อนข้อมูล − อาร์เรย์ ={5, 1, 9, 2, -1, 7}

ผลผลิต − 24

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

วิธีแก้ไขปัญหานี้คือการค้นหาองค์ประกอบขั้นต่ำของอาร์เรย์แล้วค้นหาผลรวมขององค์ประกอบที่เหลือทั้งหมดของอาร์เรย์

แต่ในที่นี้ ไม่มีการนำเงื่อนไขการนำองค์ประกอบออก อัลกอริทึมของ kadane จะแก้ปัญหาในทางที่ดีขึ้น ดังนั้น ที่นี่เราจะคำนวณผลรวมสูงสุดในลักษณะที่เราจะพบองค์ประกอบ sum ถึง ith ตั้งแต่เริ่มต้นและสิ้นสุดด้วย

จากนั้นตรวจสอบว่าองค์ประกอบใดเมื่อข้ามโดยใช้อาร์เรย์ผลรวมเริ่มต้นและสิ้นสุด จากนั้นพิมพ์ผลรวมหลังจากข้ามองค์ประกอบที่กำหนด

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;
int maxSubarraySum(int array[], int n){
   int startSum[n], endSum[n];
   int maxSum = array[0], overAllMax = array[0];
   startSum[0] = array[0];
   for (int i = 1; i < n; i++){
      maxSum = max(array[i], maxSum + array[i]);
      overAllMax = max(overAllMax, maxSum);
      startSum[i] = maxSum;
   }
   maxSum = endSum[n-1] = array[n-1];
   for (int i = n-2; i >= 0; i--){
      maxSum = max(array[i], maxSum + array[i]);
      overAllMax = max(overAllMax, maxSum);
      endSum[i] = maxSum;
   }
   int SubArraySum = overAllMax;
   for (int i = 1; i < n - 1; i++)
   SubArraySum = max(SubArraySum, startSum[i - 1] + endSum[i + 1]);
   return SubArraySum;
}
int main()
{
   int array[] = {5, 7, 1, -1, 4, 2, 9};
   int n = sizeof(array) / sizeof(array[0]);
   cout<;"The maximum subarray after removing one element is "<<maxSubarraySum(array, n);
   return 0;
}

ผลลัพธ์

The maximum subarray after removing one element is 28