최대 값 연속 하위 시퀀스 알고리즘

Question

이 문제에 대한 입력은 A[1...n]의 실수입니다. 인접한 하위 시퀀스 A[i],A[i+1],...A[j]의 숫자를 모두 합하여 최대 값이 무엇인지 알아 내야합니다. A입니다. 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)이 문제를 해결 무력 솔루션이 존재하지만, 선형 시간의 문제를 해결하는 것이 가능하다.

1. 선형 시간으로 위에서 설명한 문제를 해결하는 알고리즘을 설계하십시오. 귀하의 알고리즘을 의사 코드로 제시하십시오.
2. 알고리즘이 작동하는 방법 및 이유를 간략하게 설명하십시오.
3. 알고리즘이 실제로 선형 시간으로 실행되는 이유에 대한 간략한 설명을 제공하십시오. 우리는 모든 항목을하지 않는 경우

Answer 1

는 (그래서 솔루션이 빈 부분 배열이다), 우리는 솔루션으로 0 있습니다. 규칙이있어 그 이유는 우리가 음수로 실행 합산 동안

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

약간 까다 순간은 다음과 같습니다

3, 4, 5, -1 ... 

우리는 하나 는는 그것을두고 (와 3 + 4 + 5 == 12가) 또는 걸릴 수 있습니다 곧 긍정적 인 숫자가 나타나기를 기대합니다. 곧 :

이 모호성을 해결하기 위해 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 }));