首页 > 其他分享 >最大子段和

最大子段和

时间:2024-02-04 10:58:06浏览次数:16  
标签:题目 最大 子段 个数 选择 这道 优化

这道题目跟“生日礼物”非常像,但这里必须刚好选择\(m\)个,为了没有歧义,我们认为两个不同子段一定不会挨着(就是中间必须有数)

这个状态具体一下:一定要选择第\(j\)个数

但其实我觉得这个方程是有一点问题的,\(k\)应该从\(j-2\)开始减

接下来考虑优化空间

在考虑优化时间

然后这道题目就做完了

另外,如果这道题目不要求一定选择第\(j\)个数,那么就要用前缀和,优化时间的部分会更加麻烦

标签:题目,最大,子段,个数,选择,这道,优化
From: https://www.cnblogs.com/dingxingdi/p/18005762

相关文章

  • 作为国产深度学习框架中分布式计算特性最强大的OneFlow的最大缺点是什么?
    OneFlow是国产深度学习框架中分布式计算特性最强大的,因为其原生支持分布式特性,世界上的历史中的深度学习框架唯一可以做到这一点的也就只有Google的TensorFlow和Jax了,虽然有人说Google的分布式最强也有人说Google的分布式一般,但是毋庸置疑的是OneFlow一定是国产深度学习框架中分布......
  • 费用流求解二分图最大权匹配
    二分图最大权匹配问题:有\(n_1\)个左部点,\(n_2\)个右部点,\(m\)条边,边有边权\(w_i\),表示若选择这条边就会获得\(w_i\)的收益,求获得收益最大的一种图的匹配方案。若考虑用费用流求解,建立超级源点\(S\)和超级汇点\(T\),\(S\)向每个左部点连边,流量1费用0;每个右部点向\(......
  • 求最大数字-od-python
    求最大数字题目给定一个由纯数字组成以字符串表示的数值,现要求字符串中的每个数字最多只能出现2次,超过的需要进行删除;删除某个重复的数字后,其它数字相对位置保持不变。如34533,数字3重复超过2次,需要删除其中一个3,删除第一个3后获得最大数值4533请返回经过删除操作......
  • 数论-最大公因子及其性质
    原文如果a和b为不全为零的整数,则它们的公因子的集合是一个有限的整数集,通常包括+1和-1,我们对其中最大的那个公因子感兴趣.定义2 不全为零的整数a和b的最大公因子是指能够同时整除a和b的最大整数。a和b的最大公因子记作(a,b),(有时也记作gcd(a,b),特别是在非数论的著作中我们将......
  • 现货黄金交易:如何利用杠杆,最大化投资回报?
    黄金一直以来都是投资者们青睐的避险资产,而现货黄金交易则是让投资者有机会参与到黄金市场波动中获取收益的方式之一。而在现货黄金交易中,利用杠杆可以帮助投资者在有限的资本下最大化投资回报。首先,了解杠杆交易的基本概念是至关重要的。杠杆交易是指借用资金来进行投资,以提高投......
  • leetcode85. 最大矩形
    85.最大矩形-力扣(LeetCode)参考dp求最大字串和的思想,将一维dp转化为二维的形式,将当前列的和当成一维的数进行dp即可。这题和求最大子矩阵和的dp思路一样。1classSolution{2public:3intmaximalRectangle(vector<vector<char>>&matrix){4intn=m......
  • SQL PARTITION BY 语句把一张表分组后的最大值或最小值插入另一张表里
    1.例子见前一章,目的是有分组的,只显示OrderAmount最高的(即每组只显示一列) 2.再建一个表来存储CREATETABLE[dbo].[MaxOrders]([orderid][int]NULL,[Orderdate][date]NULL,[CustomerName][varchar](100)NULL,[Customercity][varchar](100)NULL,......
  • 上下界 可行/最大/最小 网络流/费用流(有/无源汇)
    对网络的定义进行扩展,我们可以得出一堆奇奇怪怪的网络。上下界令\(Max_e\)为边\(e\)的流量上界,\(Min_e\)为边\(e\)的流量下界,一条边的流量\(f_e\)要满足\(Min_e\lef_e\leMax_e\),除此之外和普通网络流定义相同,可以发现,普通的网络就是下界为\(0\)的网络。无源汇......
  • Linux中 awk命令输出一列多个类别中 每个类别中最大的项
     001、(base)[b20223040323@admin1test]$lsa.txt(base)[b20223040323@admin1test]$cata.txt##测试数据a88a76b88c10b777c200a87c150a34b25a66##输出第一列中每一类别中值最大的项(base)[b20223040......
  • 最大连续1的个数
    485.MaxConsecutiveOnes(Easy)给定一个二进制数组,计算其中最大连续1的个数。示例1:输入:[1,1,0,1,1,1]输出:3解释:开头的两位和最后的三位都是连续1,所以最大连续1的个数是3.注意:输入的数组只包含0和1。输入数组的长度是正整数,且不超过10,000。publicint......