代码之家 › 专栏 › 技术社区 › Anuttar

leetcode问题918的逻辑混乱

number-theory math algorithm

Anuttar · 技术社区 · 2 年前

问题陈述如下: 给定长度为n的圆形整数数组nums,返回nums的非空子数组的最大可能和。圆形阵列意味着阵列的末端连接到阵列的起点。形式上,nums[i]的下一个元素是nums[(i+1)mod n],nums[i]的上一个元素为nums[[(i-1+n)mod n]。子阵列最多只能包括一次固定缓冲器nums的每个元素。形式上,对于子数组nums[i],nums[i+1]。。。,nums[j],不存在i<=k1,k2<=j,其中k1 mod n==k2 mod n。

现在,我在网上搜索了这个解决方案,发现所有不属于具有最大可能和的子数组(比如B)的元素组成的子数组形成了具有最小可能和的个子数组。我无法理解这个逻辑。有人能解释一下它是如何工作的吗?

我试图用矛盾的方式来证明这个说法,但无法得出任何结论。此外,我不明白为什么子数组A需要是最小可能和,为什么不在最小和最大之间?

1 回复 | 直到 2 年前

trincot 2 年前

由不属于具有最大可能和的子阵列(比如B)的所有元素形成的子阵列形成具有最小可能和的个子阵列。

这是真的。设为输入数组中所有元素的总和。设为子数组形成的最大和,则子数组的和必定为。

如果不表示具有最小和的子阵列,那么将存在具有小于和的另一个子阵列。但是这些值的总和不 in将大于,这是一个矛盾,因为我们从给定的事实开始是具有最大和的子阵列。

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

2 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

2 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

2 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

2 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

2 年前