程序员经验分享-hwhale

非连续元素的最大和

2024-04-05

给定一个正整数数组，从该数组中查找非连续元素的最有效算法是什么，这些元素加在一起时会产生最大总和？


动态规划？给定一个数组A[0..n], let M(i)是使用带有索引的元素的最佳解决方案0..i. Then M(-1) = 0（用于递归），M(0) = A[0], and M(i) = max(M(i - 1), M(i - 2) + A[i]) for i = 1, ..., n. M(n)是我们想要的解决方案。这是 O(n)。您可以使用另一个数组来存储对每个子问题所做的选择，从而恢复所选的实际元素。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Arrays

Algorithm

非连续元素的最大和 的相关文章

  • 从一种数字系统转换为另一种数字系统后会有多少位数字

    主要问题 有多少位数字 让我解释 我有一个二进制数 11000000 十进制数是192 转换为十进制后 它有多少位 以十进制表示 在我的示例中 它是 3 位数字 但是 这不是问题 我在互联网上搜索并找到了一种用于整数部分的算法和一种用于小数

  • 获取向量幂的有效方法

    我编写了一个代码 在数值上使用勒让德多项式直至某个高 n 阶 例如 case 8 p 6435 x 8 12012 x 6 6930 x 4 1260 x 2 35 128 return case 9 如果向量x太长这会变得很慢 我发现说之

  • 在 O(n) 时间内排序？

    我被这个问题困扰了 2周 知道如何处理它吗 令 L 为 n 个不同整数的列表 假设 L 的 x 的元素在 1 750 范围内 设计线性排序算法对 L 的元素进行排序 我已经尝试过插入排序 但我不确定我的方法是否正确 Construct an

  • 将 numpy 代码点数组与字符串相互转换

    我有一个很长的 unicode 字符串 alphabet range 0x0FFF mystr join chr random choice alphabet for in range 100 mystr re sub W mystr 我想

  • 两组点之间的最佳匹配

    I ve got two lists of points let s call them L1 P1 x1 y1 Pn xn yn and L2 P 1 x 1 y 1 P n x n y n 我的任务是找到它们点之间的最佳匹配 以最小化它

  • const 和 constexpr 数组之间的区别

    为什么有区别const and constexpr当与数组一起使用时 int const xs 1 2 3 constexpr int ys 1 2 3 int as xs 0 error int bs ys 0 fine 我希望两者都能x

  • 解开 Knuth 的结：如何重构意大利面条式代码？

    这个问题的灵感来自如何将流程图转化为实施 https stackoverflow com questions 36647765它询问如何通过算法消除goto代码中的语句 这answer https stackoverflow com a 3

  • 如何在 Smarty 中打印 json

    我从 api 获取 json 如何使用 Smarty 打印 json Json格式 first name jinu last name mk loginid email protected cdn cgi l email protectio

  • 选取散列第 N 个元素的最快方法

    我有一个大哈希表 带有字符串索引的数组 并正在寻找一个函数quickly从中选取第一个 理想情况下也是第 N 个 元素 array shift and reset 对于我的需求来说太慢了 UPDATE 我也不是在寻找基于引用的解决方案 该函

  • 更改API数据输出的布局

    我是 API 集成和 PHP 的新手 我最近将 VIN 解码器集成到我的应用程序中 在输入框中输入车辆的 VIN 选择提交 然后就会显示 API 数据库中有关该车辆的所有信息 数据存储为关联数组 其中包含类别及其相应元素 例如 对于 VIN

  • Java-如何将黑白图像加载到二进制中？

    我在 FSE 模式下使用 Java 和 swing 我想将完全黑白图像加载为二进制格式 最好是二维数组 并将其用于基于掩码的每像素碰撞检测 我什至不知道从哪里开始 过去一个小时我一直在研究 但没有找到任何相关的东西 只需将其读入Buffer

  • 使用 UISearchBar 过滤数组

    我目前正在使用以下代码来过滤数组并将结果显示在我的 tableView 中 问题是 只有当搜索与确切的单词匹配时 才会返回结果 如何更改数组过滤器以在输入时搜索每个字符 let data Mango Grape Berry Orange A

  • JS：连接数组的数组

    我如何在数组的每个子成员和数组本身上使用 Array Join 来分隔父数组的元素 以及子数组的每个元素 let arr 1 2 3 4 5 6 console log arr join Output is 1 2 3 4 5 6 Pseu

  • 有没有时间复杂度为O(N)的排序算法？

    大多数排序算法的复杂度为 O NN 或 O NlogN 来实现结果 但是 对于特定的输入集 有些算法的复杂度为 O N 我想知道是否有一种排序算法在所有情况下都具有 O N 的复杂度 如果您只能比较 检查两个项目是否为 正在排序的值 那么您

  • 读取文本文件并将列存储在数组中

    我的文件看起来像这样 01 01 5 00 1 50 7 50 02 01 4 00 3 00 12 00 02 02 3 00 4 00 12 00 03 01 4 50 3 00 13 50 03 01 7 50 2 50 18 75

  • 调整ArrayBuffer的大小

    如果我想创建一个数组缓冲区 我会写 var buff new ArrayBuffer size 但是如何调整现有缓冲区的大小呢 我的意思是 在缓冲区末尾添加更多字节 ArrayBuffer 本身没有设置 有set https develop

  • 删除二维数组C++[关闭]

    Closed 这个问题需要细节或清晰度 help closed questions 目前不接受答案 这两种释放二维数组的方法是否相似 int M new int 5 for int i 0 i lt 5 i M i new int 3 fo

  • Redim Preserve 给出“下标超出范围”

    我想要Redim Preserve一个数组我不断收到错误 下标超出范围 我知道只有最后一个维度的大小可以更改 这正是我正在做的事情 这里出了什么问题 数组的类型是Variant BmMatrix Sheets BENCH Range a60

  • Swift 使用哪种通用排序算法？它在排序数据上表现不佳

    我一直在挑选和探索 Swift 标准库sort 其函数为Array类型 令我惊讶的是 我注意到它在已经排序的数据上表现不佳 对数组进行排序Int打乱顺序似乎比对已经排序的同一个数组进行排序快 5 倍 对已打乱顺序的对象数组进行排序比对已按排

  • 将数组作为参数传递

    如果我们修改作为方法内参数传递的数组的内容 则修改是在参数的副本而不是原始参数上完成的 因此结果不可见 当我们调用具有引用类型参数的方法时 会发生什么过程 这是我想问的代码示例 using System namespace Value Re

随机推荐

  • Twitter 客户端中的自动链接@提及

    我正在构建一个基本的 Twitter 客户端应用程序 我正在尝试弄清楚如何使保存推文的 TextView 自动链接 提及 以便它们链接到任何人的 Twitter 页面 就像在 Twitter 网站上一样 我的猜测是 这将涉及制作一个自定义

  • 使用 Python evdev 模拟按住控制器 dpad 按钮

    我正在尝试使用 Python evdev 模拟按住控制器上的 DPad 按钮 到目前为止 我已经成功按下一个按钮 如下所示 import os import time from evdev import uinput ecodes as e

  • Active Records 按 ID 排序[重复]

    这个问题在这里已经有答案了 如果我有 id 为 1 2 3 4 的记录 并且想要以某种方式对它们进行排序 例如 1 4 2 3 我该怎么做 我想类似的东西 但它当然行不通 Service all order id 1 4 2 3 贾斯汀 韦

  • JVM 在 OutOfMemoryError 之后是否自行终止 [重复]

    这个问题在这里已经有答案了 发生 OutOfMemoryError 后 JVM 会自行终止吗 如果不是那么为什么 它会尝试收回资源吗 还是有其他原因 OutOfMemoryError 不会终止 JVM 如果它未被捕获 它将终止引发错误的线程

  • angularjs 获取表单操作并提交给它

    我有一个表单 我想捕获它的提交 检查数据的验证 然后将表单提交到 HTML 表单内的操作 div div

  • Jquery 验证自定义错误消息位置

    这看起来很简单 但我无法弄清楚 我正在使用 jquery 验证插件 我正在尝试验证

  • 从点列表中获取两个最近的点

    我得到了一个整数 浮点数列表 我需要找到最接近的两个数字 我将如何仅使用嵌套 for 循环来做到这一点 如果点是一维的 就像您的输入只是一个数字列表 例如 1 4 6 2 那么你可以通过对它们进行排序并找到差异最小的在 O n log n

  • Reactjs - redux 表单和材质 UI 框架 - 具有自动类型 - 和清除字段功能

    我正在构建一个使用 redux 表单和材料 ui 框架的嵌套表单框架 迄今为止我已经在这里构建了组件 https codesandbox io s heuristic hopper lzekw https codesandbox io s

  • 在 GWT 中使数据网格的行可拖动

    我想制作一个数据网格 其中的行可以拖动 以便人们可以通过拖动行来上下移动行 由于数据网格的行将作为元素获取 我知道如何使小部件可拖动 但是如何使数据网格的行可拖动 我不想使用任何额外的插件或库来实现此目的 我所知道的唯一支持单元格小部件拖放

  • 如何配置 Hibernate 以立即应用所有保存、更新和删除？

    我该如何配置休眠 http www hibernate org 在会话执行每个操作后立即将所有保存 更新和删除应用到数据库服务器 默认情况下 Hibernate 将所有保存 更新和删除操作排入队列 并仅在经过一段时间后才将它们提交到数据库服

  • Scala：列表 [Tuple3] 到映射 [字符串，字符串]

    我得到的查询结果为List Int String Double 我需要将其转换为Map String String 用于在 html 选择列表中显示 我的破解方案是 val prices dao getPricing flatMap cas

  • 使用 Redux Observable 等待操作序列

    我有一个用例 在使用 Redux Observables 调度另一个操作之前 我需要等待一系列操作 我见过一些类似的问题 但我无法理解如何在给定的用例中使用这些方法 本质上我想做这样的事情 action ofType PAGINATION

  • 自定义内存管理器

    我正在尝试实现一个自定义内存管理器 我想知道是否有更好的方法来实现这个函数 因为当我被问及 void 指针算术时 有几个人认为如果我在 C 中有一个 void 那就太糟糕了错误的 allocates a page of memory voi

  • 为什么我的调试数据未格式化？

    var dump and print r使用 Laravel 4 时显示的数据未格式化 如何格式化数据以使其更具可读性 通过在命令行上运行以下命令将 Kint 添加到您的composer json composer require rave

  • Metamask 停止注入 web3.js

    据我们所知 从2020年1月13日开始 metamask将不再注入web3 js 我们应该采取哪些方法来停止对web3的依赖 另外 我们如何使用目前正在注入 web3 js 的现有 Metamask 来测试它 window ethereum

  • 为什么使用类方法而不是静态方法？ [复制]

    这个问题在这里已经有答案了 我知道他们是做什么的 并且我见过很多这两个例子 但我还没有找到一个我必须使用的例子classmethod而不是用staticmethod 最常见的例子是classmethod我见过的是用于创建新实例类本身 就像这

  • 积分运算符 quot 与 div

    类型类 Integral 有两个操作quot and div 但在 Haskell 2010 语言报告中并没有具体说明它们应该做什么 假如说div是积分除法 什么quot不同 或者目的是什么quot 什么时候使用其中一个 什么时候使用另一个

  • 生成生成集的算法

    给定此输入 1 2 3 4 我想生成一组跨越集 1 2 3 4 1 2 3 4 1 2 3 4 1 3 2 4 1 2 3 4 1 3 2 4 1 4 2 3 1 2 3 4 1 3 2 4 1 4 2 3 1 2 3 4 1 2 4 3

  • 如何在 django 2.0 管理中使用allow_tags？

    Support for the allow tags attribute on ModelAdmin methods is removed 刚刚找到答案 使用mark safe https docs djangoproject com en

  • 非连续元素的最大和

    给定一个正整数数组 从该数组中查找非连续元素的最有效算法是什么 这些元素加在一起时会产生最大总和 动态规划 给定一个数组A 0 n let M i 是使用带有索引的元素的最佳解决方案0 i Then M 1 0 用于递归 M 0 A 0 a

热门标签