0

昨天在 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对于这种情况，这是最大可能的

4

3 回答 3

2

如果我们可以从数组中找到最小序列，那么如果我们乘以 1，则该部分将为您提供最大总和。

例如在这个例子中：-2 3 -1 -4 -2最小序列是-1、-4、-2。如果我们将此序列乘以 1，它将使总和最大化。所以问题是如何找到最小和序列。

O(N) 解决方案来了：

如果数组包含所有 +ve，则没有子数组需要乘以 -1。检查以下问题。 Kadane 算法在 O(N) 中的最小和子数组

于 2013-10-25T07:02:43.317 回答
0

如果我正确理解您的问题，听起来您想首先找到最小子数组，然后将其乘以 -1 并添加剩余的非否定值。

最小子数组本质上与最大子数组问题相反：

public class MaxSumTest {
    public static class MaxSumList{
        int s=0, e=0;
        List<Integer> maxList;

        public MaxSumList(List<Integer> l){
            //Calculate s and e indexes
            minSubarray(l);

            //Negate the minSubarray
            for(int i=s; i < e; i++)
                l.set(i, -l.get(i));

            //Store list
            maxList = l;
        }

        public int minSubarray(List<Integer> l){
            int tmpStart = s;
            int currMin = l.get(0);
            int globalMin = l.get(0);

            for(int i=1; i<l.size(); i++){
                if(currMin + l.get(i) > 0){
                    currMin = l.get(i);
                    tmpStart = i;
                }
                else{
                    currMin += l.get(i);
                }
                if(currMin < globalMin){
                    globalMin = currMin;
                    s = tmpStart;
                    e = i+1;
                }
            }
            return globalMin;
        }
    }
    public static void main(String... args){
        MaxSumList ms = new MaxSumList(Arrays.asList(new Integer[]{-2, 3, -1, -4, -2}));
        //Prints [-2, 3, 1, 4, 2]
        System.out.println(ms.maxList);
    }
}
于 2013-10-25T07:13:13.017 回答
0

您显示的算法基本上计算了任何元素的最大总和和当前总和。

注意：它构建与原始元素符号相反的数组。

如果当前总和为负，则拒绝原始总和并使用新元素开始新总和。

如果当前总和为正，则意味着包括先前的条目是有益的，它将当前元素添加到总和中。

于 2013-10-25T06:51:25.820 回答