假设我们有一个包含一些整数的数组(可以是 +ve 和 -ve)。
我们从中找到非空的最大和最小子数组(子数组只有连续的元素)。
我的主张是这些子数组要么是不相交的(没有公共元素),要么一个完全包含另一个。不可能有像部分交叉这样的东西。
这种说法是真的吗?如果不能,你能举个反例吗?
示例:13 -3 -25 20 -3 -16 -23 18 20 -7 12 -5 -22 15 -4 7
最大子数组是从第 8 到第 11 个元素,总和为 43。最小子数组是从第 2 到第 7 个元素,总和为 -50。