ผลรวม Subarray สูงสุดพร้อมการลบหนึ่งครั้งใน C++

สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม เราต้องหาผลรวมสูงสุดสำหรับ subarray ที่ไม่ว่างเปล่า (องค์ประกอบที่ต่อเนื่องกัน) โดยมีการลบองค์ประกอบไม่เกินหนึ่งรายการ กล่าวอีกนัยหนึ่ง เราสามารถพูดได้ว่าเราต้องการเลือกอาร์เรย์ย่อยและเลือกที่จะลบหนึ่งองค์ประกอบออกจากมัน เพื่อให้ยังมีองค์ประกอบเหลืออย่างน้อยหนึ่งองค์ประกอบ และผลรวมขององค์ประกอบที่เหลือจะสูงสุด เราต้องจำไว้ว่า subarray จะต้องไม่ว่างเปล่าหลังจากลบหนึ่งองค์ประกอบ ดังนั้นหากอินพุตเป็น [1,-2,0,3] ผลลัพธ์จะเป็น 4 ดังนั้นหากเราลบ -2 มันจะคืนค่าผลรวมสูงสุด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของอาร์เรย์ และ :=a[0]
• suff_with_del :=0, suff_with_out_del :=a[0]
• สำหรับ i ในช่วง i ถึง n – 1
  • suff_with_del :=สูงสุดของ suff_with_del + a[i] และ suff_with_out_del
  • suff_with_out_del :=สูงสุดของ a[i] และ suff_with_out_del + a[i]
  • ans :=สูงสุดของ ans, suff_with_out_del และ suff_with _del
• ผลตอบแทน

ตัวอย่าง(C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int maximumSum(vector<int>& a) {
      int n = a.size();
      int ans = a[0];
      int suffix_with_deletion = 0;
      int suffix_with_not_deletion = a[0];
      for(int i = 1;i<n;i++){
         suffix_with_deletion = max(suffix_with_deletion + a[i], suffix_with_not_deletion);
         suffix_with_not_deletion = max(a[i],suffix_with_not_deletion+a[i]);
         ans = max({ans, suffix_with_not_deletion,suffix_with_deletion});
      }
      return ans;
   }
};
main(){
   vector<int> v = {1,-2,0,3};
   Solution ob;
   cout <<ob.maximumSum(v);
}

อินพุต

[1,-2,0,3]

ผลลัพธ์

4