C++에서 한 번의 삭제로 최대 하위 배열 합계

정수 배열이 있다고 가정합니다. 최대 하나의 요소 삭제가 있는 비어 있지 않은 하위 배열(연속 요소)의 최대 합계를 찾아야 합니다. 다시 말해, 하위 배열을 선택하고 선택적으로 하나의 요소를 삭제하여 최소한 하나의 요소가 남아 있고 나머지 요소의 합이 최대가 되도록 하고 싶다고 말할 수 있습니다. 한 요소를 삭제한 후 하위 배열이 비어 있지 않아야 함을 명심해야 합니다. 따라서 입력이 [1,-2,0,3]과 같으면 출력은 4가 됩니다. 따라서 -2를 삭제하면 최대 합계가 반환됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=배열 크기 및 :=a[0]
suff_with_del :=0, suff_with_out_del :=a[0]
i ~ n – 1 범위의 i에 대해
- 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]