最大值連續子序列算法

此問題的輸入是實數的數組A[1...n]。您需要找出通過總結A的連續子序列A[i],A[i+1],...A[j]的所有數字可以獲得的最高值。如果A不包含負數，則問題很簡單，可以通過總結A的所有元素來解決。當A包含正數和負數的混合時，它變得更加棘手。最大值連續子序列算法

例如，對於A = [-2,11,-4,13,-5,-3]，解決方案是20（11-4 + 13 = 20）。對於A = [-2,1,-3,4,-1,2,1,-5,4]，解決方案是6（4-1 + 2 + 1 = 6）。空子序列號的總和爲0。

存在一個蠻力解決方案，解決了在爲O（n^3）這個問題，但它也可以解決線性時間的問題。

設計一個算法來解決線性時間上面描述的問題。以僞代碼的形式呈現您的算法。
簡要說明算法的工作原理和原因。
給出一個簡單的解釋，說明爲什麼你的算法確實在線性時間運行。

來源

2016-12-12 soapzi

如果我們不採取任何項目（因此該解決方案是一個空的子陣），我們有0作爲解決方案。這就是爲什麼規則是：

When running `sum` drops to `0` or below, restart summing.

有點棘手的時刻是在總結我們碰到一個負數：

3, 4, 5, -1 ...

我們可以離開它（並有3 + 4 + 5 == 12）或起飛它希望正數將很快出現：

3, 4, 5, -1, 100, 200, 300

爲了解決這個模棱兩可的問題，我們可以記住最好的sum，直到result並繼續求和。 C＃實現：

private static double Solution(IEnumerable<double> source) { 
    // We can guarantee 0 (for empty subarray) 
    double result = 0; 
    double sum = 0; 

    // Linear: all we have to do is to scan the collection 
    foreach (var item in source) 
    if (sum + item <= 0) // when sum drops to zero 
     sum = 0;   // ... restart summing 
    else { 
     sum += item; 

     if (sum > result) // update the best sum so far on each decision 
     result = sum; 
    } 

    return result; 
}

測試：

// 6 
Console.WriteLine(Solution(new double[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 })); 
// 20 
Console.WriteLine(Solution(new double[] { -2, 11, -4, 13, -5, -3 }));

來源

2016-12-12 07:51:14

最大值連續子序列算法

回答

相關問題