[C#] 백준 1912번 문제풀이

문제번호: 1912

문제명: 연속

문제링크: https://www.acmicpc.net/problem/1912

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다

 

오늘은 최대 연속 구간합을 구하는 문제를 풀었습니다. 해당 문제의 시간제한부터 살펴보겠습니다.
1초 (추가 시간 없음)이네요. 완전탐색(O(n^3))으로 풀기엔 시간이 턱없이 부족하다고 판단했습니다. 그래서 동적할당(dp)로 접근을 시도했습니다. thisSum과 maxSum 변수를 이용해 thisSum = Math.Max(thisSum + arr[k], 0); 으로 자신과 arr[k]을 더한값을 0과 비교하여 값을 할당하고, maxSum = Math.Max(maxSum, thisSum); 으로 최댓값을 할당했습니다. 마지막으로 maxSum이 0일경우 모든 수가 음수이라는 뜻이기 때문에 가장 작은 수를 정답으로 출력해주었습니다.
다음은 정답코드입니다.

static void Main()
{
    using StreamReader sr = new StreamReader(Console.OpenStandardInput());
    using StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    int n = int.Parse(sr.ReadLine());
    int[] nums = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
    sw.WriteLine(MaxSubArray(nums, n));
}

static int MaxSubArray(int[] arr, int n)
{
    if (n == 1)
        return arr[0];

    int maxSum, thisSum;
    maxSum = 0;
    thisSum = 0;

    for (int k = 0; k < n; k++)
    {
        thisSum = Math.Max(thisSum + arr[k], 0);
        maxSum = Math.Max(maxSum, thisSum);
    }

    if (maxSum == 0)
        return arr.Max();
    return maxSum;
}