昨天在 Codechef 上有一个在线编码活动,我不知道如何解决其中的一个问题。简单地说:
给定N个数字 { a 1 , a 2 , ..., a N } 的列表,找到使总和 ( a 1 + ... + a L−1 ) 最大化的 范围 [ L , R ] (1 ≤ L ≤ R ≤ N ) ) - (一L + … + 一R ) + (一R +1 + … + 一N )。
换句话说,您可以将列表的一个子部分乘以 -1,并希望最大化结果列表的总和。
我看了一些这样的解决方案,但无法弄清楚这个人在做什么。
我该怎么办?
例子
-2 3 -1 -4 -2
现在您可以将第 3 到 5 小节乘以 -1 得到
-2 3 1 4 2
这样sum(-2,3,1,4,2) = 8
对于这种情况,这是最大可能的