Bc8两个最大子串和

BC8两个最大子串和

BC8两个最大子串和

题目:对于一个包含负值的数字串array[1...n],要找到它的两个子串

array1[0...s1](0<=s1<=i<n)和array2[i <s2...<= n-1]

使得array1[0...s1]和array2[s2...n]两个子串的和最大。


分析:


给定的数字串里有正数、也有负数。子串的和最大,所以不考虑负数部分。

看了下子串的取值范围,要最大的话,子串1从0到i,子串2,从大于i的第一个数 到 n-1。那么key值就是数字串的正数和减去最大值(都是整数,不考虑小数)。


结果,提交答案是错的。

看答案:这题主要是题意没表述好,导致不少人理解错,以为第一个串必须从array[0]开始、第二个串必须以arrry[n-1]结束、两串没有交集,这样得到的结果就是2693。

其实理解为0<=s1<s2<n。

我认输,这样的题目还有什么好说的。。