你有一个包含整数的数组a,数组中的每个元素可以是正数、负数或零。
现在,你拥有一种特殊的能力:
你可以选择数组中的任意一段连续的子数组,并将这段子数组内的每个数字都变换成其相反数。这个操作可以执行0次或1次。
你的任务是,利用这个特殊能力,找出在执行操作后能够达到的最大和的连续子数组。这里所指的“最大和"是指经过可能的变换操作后,任意连续子数组元素之和的最大值。需要注意的是,最终选择的子数组至少应包含一个元素。注意:取反的子数组跟最终求和的子数组并不需要相同
给定一个长度为n的整数数组a(元素可为正、负或零),你拥有一次“取反”操作的能力:可以任选一个连续子数组,将其中每个元素都变为相反数。该操作最多执行一次(也可不执行)。操作之后,你再任选一个非空的连续子数组,取其元素之和。问:通过恰当地选择取反区间(或不取反)以及最后取和的区间,能够获得的最大子数组和是多少?
我们需要在“取反”与“取和”两个自由度下同时优化。令最终选取的求和区间为 [L,R],取反区间为 [l,r]。如果取反区间与求和区间有重叠,就会对被重叠部分产生符号翻转;如果无重叠,取反操作对求和区间无影响。枚举两者在 O(n2) 当然不可行。