兩個最大的連續子數組

我目前正在做一個類似於最大連續子數組問題的問題。但是，不是隻找到一個連續的子數組，而是可以找到兩個不重疊的連續子數組。兩個最大的連續子數組

例如對於下面的測試案例，答案是20，因爲我們可以採取一切，但-20。

5 3 -20 4 8

要做到這一點，我實現了下面的代碼：

long long n, nums[500500], dp[500500][2][3]; 

long long best(int numsLeft, int beenTaking, int arrLeft) { 
    if (arrLeft < 0 || numsLeft < 0) return 0; 

    if (dp[numsLeft][beenTaking][arrLeft] != -1) 
     return dp[numsLeft][beenTaking][arrLeft]; 

    if (beenTaking) { 
     // continue Taking 
     long long c1 = best(numsLeft - 1, beenTaking, arrLeft) + nums[numsLeft]; 
     // stop Taking 
     long long c2 = best(numsLeft - 1, 0, arrLeft); 

     return dp[numsLeft][beenTaking][arrLeft] = max(c1, c2); 
    } else { 
     // continue not Taking 
     long long c1 = best(numsLeft - 1, beenTaking, arrLeft); 
     // start Taking 
     long long c2 = best(numsLeft - 1, 1, arrLeft - 1) + nums[numsLeft]; 

     return dp[numsLeft][beenTaking][arrLeft] = max(c1,c2); 
    } 
}

這是函數調用：

cout << best(n - 1, 0, 2) << endl;

的DP陣列已-1填充在函數調用前。 nums數組包含n個元素並且是零索引的。

Ideone.com鏈接是這樣的：http://ideone.com/P5PB7h

雖然我的代碼不上面顯示的樣品測試工作的情況下，它沒有一些其他的測試用例（即不能提供給我）。是否有任何邊緣案例未被我的代碼捕獲？我哪裏錯了？感謝您的幫助。

我試圖想出一些這樣的邊緣情況，但我無法這樣做。

來源

2017-01-01 Mohideen Imran Khan

對不起，你必須得到測試輸入與哪個代碼失敗 –

long long n，nums [500500]，dp [500500] [2] [3]; - 這是22兆字節的靜態存儲被佔用如果'sizeof（long long）'== 8），可能會根據聲明的位置來決定堆棧空間。考慮使用'std :: vector'。 – PaulMcKenzie

*對於其他一些測試用例（我無法使用它）失敗* - 在現實世界中，我們有測試用例，其中程序被認爲是失敗的。 – PaulMcKenzie

這個問題似乎是對下面的行：

if (beenTaking) { 
    // continue Taking 
    long long c1 = best(numsLeft - 1, beenTaking, arrLeft) + nums[numsLeft]; 
    ... 
} else { 
    ... 
}

添加best(numsLeft - 1, 1, arrLeft)不遞減arrLeft意味着從第一numsLeft - 1值nums[]「最好」結果發生在NUMS []的端部（在索引numsLeft - 1）。這可能不是真的。

如果超過2個以負值分隔的正範圍，代碼可能會失敗。

而且，dp數組應該被初始化爲某種明顯超出範圍的內容，如LLONG_MIN，而不是-1，這可能是一個合法的總和。

來源

2017-01-01 06:46:25 Edy

爲了調試的目的，我完全刪除了備忘錄，並將'arrLeft'更改爲'arrLeft - 1'，但即使是簡單的例子，例如'5 5 5 -5 5 5'' 我得到15當答案應該是25（原始代碼給出正確的答案）。 –

您問您錯過了哪些邊緣案例。這正是我想要回答的。我沒有說（或者知道）正確的解決方案應該基於你的代碼。但是，如果您在方向上進行調試，並將初始化更改爲LLONG_MIN，則應該可以找到它。 – Edy

兩個最大的連續子數組

回答

相關問題