가능한 모든 배열 요소들을 Brute Fource 방식으로 합계를 구한다면, 배열 크기 N 에 대해 N*N의 합계(O(N^2))를 구해야 한다. 최적화된 솔루션은 처음부터 계속 배열 요소를 더하면서 이전 최대값과 비교하여 새로운 최대값을 구하는 방식이다. 이 때 키포인트는 계속 더해 나가는 합계(아래의 예에서는 tempSum)가 음수가 나오는 경우, 이는 남은 정수들 합을 구하는데 플러스 역활을 하지 않으므로, 이를 0로 Reset한다는 점이다.

public void RunTest()
{
    int[] a = { 3, -4, 5, 2, -5, 5, 9, -8, -2, 8 };
    int result = MaxSumOfSubarray(a);
    Console.WriteLine(result);
}

int MaxSumOfSubarray(int[] a)
{
    int max = 0;
    int tempSum = 0;

    for (int i = 0; i < a.Length; i++)
    {
        tempSum += a[i];
        tempSum = Math.Max(tempSum, 0);
        max = Math.Max(max, tempSum);
    }

    return max;
}