using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        //List<int> A = new List<int>{-2, 1, -3, 4, -1, 2, 1, -5, 4};

        //int sum = maxSubArray(A);

        //Console.WriteLine("sum: " + sum);

        //List<int> A = new List<int>{3, 7, 5, 20, -10, 0, 12};

        //int B = 2;

        //int least = LeastAvarage(A,B);

        //Console.WriteLine("least: " + least);

        int A = 1;

        int B = 75;

        List<int> C = new List<int>{4};

        int max = maxSubarray(A,B,C);

        Console.WriteLine("max: " + max);

    }

    public static int maxSubarray(int A, int B, List<int> C) {

        int curr = C[0];

        int maxs = 0, l = 0;

        for(int i = 0; i < C.Count; i++)

        {

            if(curr <= B)

            {

                maxs = Math.Max(maxs, curr);

            }

            while(curr + C[i] > B && l < i )

            {

                curr -= C[l];

                l++;

            }

            curr += C[i];

        }

        if(curr <= B)

        {

            maxs  = Math.Max(maxs, curr);

        }

        return maxs;

    }

    public static int LeastAvarage(List<int> A, int B) {

        int n = A.Count;

        int index = 0, curr = 0;

        for(int i = 0; i < B; i++)

        {

            curr += A[i];

        }

​

        int sum = curr;

​

        for(int i = B; i < n; i++)

        {

            curr += A[i] - A[i-B];

​

            if(curr < sum)

            {

                sum = curr;

                index = i - B + 1;

            }

        }

        return index;

        //Console.WriteLine("A[" + i + "] = " + A[i] + ", sum = " + sum + ", least: " + least + ", index: " + index);

    }

    public static int maxSubArray(List<int> A) {

        int n = A.Count;

        int max = int.MinValue;

        int curr = 0;

        for(int i = 0; i < n; i++)

        {

            curr = curr + A[i];

            max = Math.Max(curr, max);

            Console.WriteLine("A[" + i + "] = " + A[i] + ", curr = " + curr + ", max = " + max);

            curr = Math.Max(curr, 0);

            Console.WriteLine(" -- >  curr = " + curr );

        }

        return max;

    }

}