using System;

using System.Linq;

using System.Collections.Generic;

using System.Text;

​

/*

​

**************** This is optimized Solution (UNDER CONSTRUCTION) *****************

​

Link: [https://www.scaler.com/academy/mentee-dashboard/class/28326/assignment/problems/56?navref=cl_tt_lst_nm]

​

Problem Description

​

Find the contiguous non-empty subarray within an array, A of length N, with the largest sum.

​

Problem Constraints

1 <= N <= 1e6

-1000 <= A[i] <= 1000

​

Input Format

The first and the only argument contains an integer array, A.

​

Output Format

Return an integer representing the maximum possible sum of the contiguous subarray.

​

Example Input

Input 1:

​

 A = [1, 2, 3, 4, -10] 

Input 2:

​

 A = [-2, 1, -3, 4, -1, 2, 1, -5, 4] 

​

Example Output

Output 1:

​

 10 

Output 2:

​

 6 

​

Example Explanation

Explanation 1:

​

 The subarray [1, 2, 3, 4] has the maximum possible sum of 10. 

Explanation 2:

​

 The subarray [4,-1,2,1] has the maximum possible sum of 6.

*/

​

public class Program

{

    private static int maxSubArray(List<int> A)

    {

        int _arrCount = A.Count;

        int max_Sum = A.Max(); //int.MinValue;

        Console.WriteLine("The max Value from the array is: " + max_Sum);

        int _currSum = 0;

        for(var i = 0; i < _arrCount; i++){

            if(A[i] > 0){

                _currSum += A[i];

                /*Re-check Max Sum Logic*/

                if(_currSum > max_Sum) {

                    max_Sum = _currSum;

                }

            }else{

                int _tmp =  _currSum + A[i];

                _currSum = (_tmp > 0) ? _tmp : 0;

            }

        }

        return max_Sum;

    }

    public static void Main()

    {

        //List<int> _inputArray = new List<int>(){ 1, 2, 3, 4, -10 };

        //List<int> _inputArray = new List<int>(){ 1, 2, 3, 4, -10 };

        //List<int> _inputArray = new List<int>(){ 4, -1, 2, 1 };

        //List<int> _inputArray = new List<int>(){ -20, -500, -45 };

        List<int> _inputArray = new List<int>(){ -2, 1, -3, 4, -1, 2, 1, -5, 4 };

        int _maxSum = Program.maxSubArray(_inputArray);

        Console.WriteLine("The maximum sum of a contiguous sub-Array is: " + _maxSum);

    }

}