需要帮助理解逻辑算法

昨天有一个在线编码事件上Codechef，我无法弄清楚如何解决one of the questions from it。简单的讲：需要帮助理解逻辑算法

鉴于Ñ数字{ 一个，一个，＆hellip;，一个_Ñ }，查找范围[大号的列表，R]（1 ≤ L ≤ - [R ≤ Ñ）最大化的总和（一个 + ＆hellip; + 一个_{大号） − （一个_大号 + ＆hellip; + 一个_ř） + （一个_{- [R +1} + ＆hellip; + 一个_Ñ）。}

换句话说，你会得到通过− 1乘以列表的款，并希望最大限度的结果列表的总和。

我看着几个像this的解决方案，但无法弄清楚这家伙在做什么。

我该怎么办？

例

-2 3 -1 -4 -2

现在你可以乘以-1的第3〜5得到

-2 3 1 4 2

使得sum(-2,3,1,4,2) = 8这是最大可能为这种情况下

来源

2013-10-25 Insane Coder

这个问题将是垃圾当链路过时 –

链接的工作正常 –

@InsaneCoder如果什么网站管理员删除页面？ – Rohit

如果我们可以从数组中找到最小序列而不是那个部分，如果我们乘以一个将会给出最大和。

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

这里落入O（N）溶液：

否定每隔数
并运行kadane's algorithm

如果数组包含所有雾化+ ve比没有子阵列需要被乘以乘以-1。检查下面的问题。 minimum sum subarray in O(N) by Kadane's algorithm

来源

2013-10-25 07:02:43 Trying

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

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

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

如果当前总和是正数，那么这意味着包括以前的条目是有益的，它将当前元素添加到总和。

来源

2013-10-25 06:51:25

你能提出一个更好的任务算法 –

@InsaneCoder该算法已经O（N）时间复杂度。任何其他算法至少应该具有这样的时间复杂度。 –

我的意思是不同的策略 –

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

最小的子阵本质上是maximum subarray problem相反：

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-25 07:13:13 bcorso

需要帮助理解逻辑算法

回答

相关问题