Tổng chuỗi con bị ràng buộc trong C ++

Giả sử chúng ta có một mảng gọi là nums và một số nguyên k, chúng ta phải tìm tổng lớn nhất của một dãy con không rỗng của mảng đó sao cho cứ hai số liên tiếp trong dãy con, nums [i] và nums [j], trong đó i

Như chúng ta biết, một dãy con của một mảng có được bằng cách xóa một số phần tử khỏi mảng, giữ lại các phần tử còn lại theo thứ tự ban đầu của chúng.

Vì vậy, nếu đầu vào là [10,2, -9,5,19] và k =2, thì đầu ra sẽ là 36 vì dãy con là [10,2,5,19].

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

ret:=-inf
Xác định một mảng dp và sao chép mảng đã cho vào đó
Xác định một dq deque
chèn v [0] vào đầu dq
n:=kích thước của v
ret:=v [0]
để khởi tạo i:=1, khi i
- nếu i> k và phần tử đầu tiên của dq giống với dp [i - k - 1], thì
  - xóa phần tử phía trước khỏi dq
- dp [i]:=tối đa của dp [i] và (nếu dq trống thì dp [i] + 0, nếu không thì phần tử đầu tiên của dp + dq [i])
- while (không phải dq trống và phần tử cuối cùng của dq
  - xóa phần tử cuối cùng khỏi dq
- chèn dp [i] vào cuối dq
- ret:=tối đa ret và dp [i]
trả lại ret

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

Ví dụ

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 10;
class Solution {
   public:
   int constrainedSubsetSum(vector<int>& v, int k) {
      int ret = -inf;
      vector<int> dp(v.begin(), v.end());
      deque<int> dq;
      dq.push_front(v[0]);
      int n = v.size();
      ret = v[0];
      for (int i = 1; i < n; i++) {
         if (i > k && dq.front() == dp[i - k - 1])
         dq.pop_front();
         dp[i] = max(dp[i], dq.empty() ? dp[i] + 0 : dp[i] +
         dq.front());
         while (!dq.empty() && dq.back() < dp[i])
         dq.pop_back();
         dq.push_back(dp[i]);
         ret = max(ret, dp[i]);
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {10,2,-9,5,19};
   cout << (ob.constrainedSubsetSum(v, 2));
}

Đầu vào

{10,2,-9,5,19}, 2

Tổng chuỗi con bị ràng buộc trong C ++

Ví dụ

Đầu vào

Đầu ra