/*

Problem: 

Given an integer array nums, find the maximum sum subarray with atleast 1 element and return its sum

​

Ex: 

Input : [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

​

Input: [5,4,-1,7,8]

Output: 23

*/

​

​

​

using System;

public class Program

{

    public static void Main()

    {

    }

    public static int GetSum(int[] nums)

    {

        if(nums.Length == 1)

            return nums[0];

​

        int sum = nums[0];

        int maxSum = sum;

        for(int i = 1; i < nums.Length; i++)

        {

            sum = Math.Max(sum + nums[i], nums[i]);

            maxSum = Math.Max(sum, maxSum);

        }

        return maxSum;

        // Note: Best way here was to initialize sum to first variable

        // Mistake: Initilized sum to 0 -> This fails for inputs with all negative numbers!

        // Mistake: Initialize sum to Int32.MinValue -> you can't add or subtract to infinity!

    }

}