当前位置: 首页 > 编程笔记 >

C ++中的约束子序列总和

公良光熙
2023-03-14
本文向大家介绍C ++中的约束子序列总和,包括了C ++中的约束子序列总和的使用技巧和注意事项,需要的朋友参考一下

假设我们有一个名为nums的数组和一个整数k,我们必须找到该数组的一个非空子序列的最大和,以使子序列中每两个连续的数字nums [i]和nums [j],其中i <j,条件j-i <= k为真。

众所周知,数组的子序列是通过从数组中删除一些元素而获得的,其余元素则保持其原始顺序。

因此,如果输入像[10,2,-9,5,19]且k = 2,则由于子序列为[10,2,5,19],输出将为36。

为了解决这个问题,我们将遵循以下步骤-

  • ret:= -inf

  • 定义一个数组dp并将给定的数组复制到其中

  • 定义一个双端队列dq

  • 在dq的开头插入v [0]

  • n:= v的大小

  • ret:= v [0]

  • 对于初始化i:= 1,当i <n时,更新(将i增加1),-

    • 从dq中删除最后一个元素

    • 从dq中删除前元素

    • 如果i> k并且dq的第一个元素与dp [i-k-1]相同,则

    • dp [i]:= dp [i]的最大值,并且(如果dq为空,则dp [i] + 0,否则为dp + dq [i]的第一个元素)

    • 而(不是dq为空,并且dq的最后一个元素<dp [i]),则执行-

    • 在dq的末尾插入dp [i]

    • ret:= ret和dp [i]的最大值

    • 返回ret

    让我们看下面的实现以更好地理解-

    示例

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

    输入项

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

    输出结果

    36
     类似资料:
    • 我有这样的情况: 由于项目经理之间存在关系m:n,我将有第三个表: 其中(ManagerID,ProjectID)是Manager_has_Project的复合主键 让我们假设我们必须删除一个从我们的数据库中创建了一些项目的经理:SQL不会让我们这么做。我们可以在子表“on DELETE cascade”中添加对fk ManagerID的约束,但在这种情况下,我们将丢失有关(例如)有多少经理为一个

    • 我在项目中使用Spring数据,并使用JPA在实体和表之间进行映射,这是我的实体 这是我的回购 当我尝试保存时,我遇到了以下问题:

    • 问题内容: 我正在将SEAM 2 / Hibernate与PostgreSQL 9数据库一起使用。我有下表 我想添加一个约束,以确保每个新条目都具有active_band_user和active_band_date的唯一组合。 每秒可能有许多次尝试插入,因此我需要尽可能地提高效率,是否可以在实体映射中使用SEAM /hibernate注释? 提前致谢 问题答案: 没有Hibernate注释在插入/

    • 我希望将clob列的约束更改为约束。但是,当尝试 或 我做错了什么?在这种情况下,我也必须使用临时栏吗?我知道使用temp列将数据类型从clob更改为varchar2的场景,但这里我只想更改约束。为什么这是不可能的? 提前感谢!

    • 问题内容: 在MySQL中创建非NULL约束以使fieldA和fieldB不能都为NULL的最佳方法是什么。我不在乎任何一个本身是否为NULL,只要另一个字段具有非NULL值即可。而且,如果它们都具有非NULL值,那就更好了。 问题答案: MySQL 5.5引入了SIGNAL,因此我们不再需要Bill Karwin的答案中的额外列。Bill指出您还需要一个更新触发器,因此我也将其包括在内。