需要幫助理解邏輯算法

昨天有一個在線編碼事件上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

需要幫助理解邏輯算法

回答

相關問題