class Program
    {
        static void Main(string[] args)
        {
            var randomizer = new Random();

            int[] checkArray;

            int expected, actual;

            bool isSumCorrect = true;

            while (isSumCorrect)
            {
                checkArray = new int[randomizer.Next(1, 100)];

                for (int i = 0; i < checkArray.Length; i++)
                {
                    checkArray[i] = randomizer.Next(-100, 100);
                }

                expected = OptimalSummator.Check(checkArray);

                actual = NonOptimalSummator.Check(checkArray);

                isSumCorrect = expected == actual;
            }
        }
    }

    static class OptimalSummator
    {
        public static int Check(int[] arr)
        {
            int local, global, current;

            local = global = current = arr[0];

            for (int i = 1; i < arr.Length; i++)
            {
                current = arr[i];

                if (local >= 0)
                {
                    local = Math.Max(0, Math.Max(current, local + current));
                }
                else
                {
                    local = Math.Max(local, current);
                }

                global = Math.Max(local, global);
            }

            return global;
        }
    }

    static class NonOptimalSummator
    {
        public static int Check(int[] arr)
        {
            int global = arr[0];
            int local;

            for(int i = 0; i < arr.Length; i++)
            {
                local = 0;

                for(int j = i; j < arr.Length; j++)
                {
                    local += arr[j];

                    global = Math.Max(global, local);
                }
            }

            return global;
        }
    }