[PS/C#] HackerRand - Algorithms - The Maximum Subarray

www.hackerrank.com/challenges/maxsubarray/problem

The Maximum Subarray | HackerRank

 

static int[] maxSubarray(int[] arr)
    {
        var maxElement = arr.Max();
        var sumPositive = arr.Any(x=>x>0);
        var maxOfSubseq = sumPositive ?  arr.Where(x=>x>0).Sum() : maxElement;

        var dp = new int[] { arr[0], arr[0] };
        var sum = arr[0];
        for (int i = 1; i < arr.Length; i++)
        {
            var max = Math.Max(dp[0] + arr[i], dp[1] + arr[i]);
            dp[0] = max;
            dp[1] = arr[i];

            var dpsMax = Math.Max(dp[0], dp[1]);

            if (dpsMax > sum)
            {
                sum = dpsMax;
            }
            
        }

        return new int[] { sum, maxOfSubseq };
    }

정말 오오오랜만에 시작한 알고리즘

문제도 쉬운편인 것으로 골랏다.

 

알고리즘은 clojure 로 푸는게 국룰인데, 같이 하는사람들이 못알아먹겠다고 징징대서 C#으로 짬 :(

For 문이 어색하다 크흠..