using System;

public class Program

{

    public static void Main()

    {

        var exampleArr = new int[] {-2, 1, -3, 4, -1, 2, 1, -5, 4};

        var exampleArr1 = new int[] {8, -1, 3, 4};

        var res = MaximumCircularSubArray(exampleArr);

        var res1 = MaximumCircularSubArray(exampleArr1);

        Console.WriteLine(res);

        Console.WriteLine(res1);

    }

    private static int MaximumSubArray(int[] arr) {

        var curMax = arr[0];

        var globalMax = arr[0];

        for (var i = 1; i < arr.Length; i++) {

            curMax = Math.Max(arr[i], curMax + arr[i]);

            globalMax = Math.Max(curMax, globalMax);

        }

        return globalMax;

    }

    private static int MinimumSubArray(int[] arr) {

        var curMin = arr[0];

        var globalMin = arr[0];

        for (var i = 1; i < arr.Length; i++) {

            curMin = Math.Min(arr[i], curMin + arr[i]);

            globalMin = Math.Min(curMin, globalMin);

        }

        return globalMin;

    }

    private static int MaximumCircularSubArray(int[] arr) {

        if (arr.Length == 0) return 0;

        bool isAllPositive = true;

        bool isAllNegative = true;

        foreach (var i in arr) {

            if (i > 0) isAllNegative = false;

            else if (i < 0) isAllPositive = false;

        }

        int maxSum = MaximumSubArray(arr);

        if (isAllPositive || isAllNegative) {

            return maxSum;

        }

        int minSum = MinimumSubArray(arr);

        int totalSum = 0;

        foreach (var i in arr) {

            totalSum += i;

        }

        return Math.Max(maxSum, totalSum - minSum);

    }

}