Tổng mảng con tối đa với một lần xóa trong C ++

Giả sử chúng ta có một mảng các số nguyên; chúng ta phải tìm tổng lớn nhất cho một mảng con không rỗng (các phần tử liền kề) với nhiều nhất một phần tử bị xóa. Nói cách khác, chúng ta có thể nói rằng chúng ta muốn chọn một mảng con và tùy chọn xóa một phần tử khỏi nó sao cho vẫn còn lại ít nhất một phần tử và tổng các phần tử còn lại là lớn nhất có thể. Chúng ta phải nhớ rằng mảng con cần phải trống sau khi xóa một phần tử. Vì vậy, nếu đầu vào là [1, -2,0,3], thì đầu ra sẽ là 4. Vì vậy, nếu chúng ta xóa -2, nó sẽ trả về tổng tối đa.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mảng và:=a [0]
• Suff_with_del:=0, Suff_with_out_del:=a [0]
• cho tôi trong phạm vi từ i đến n - 1
  • Suff_with_del:=max of Suff_with_del + a [i] và Suff_with_out_del
  • Suff_with_out_del:=tối đa a [i] và Suff_with_out_del + a [i]
  • ans:=max of ans, Suff_with_out_del và Suff_with _del
• trả lại res

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

[1,-2,0,3]

Đầu ra

4