Find the maximum sum of sub array within an array.

Problem: Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Approach: This is simple Kadane's Algorithm. Just look at the implementation to understand the approach.

Implementation in C#:

    public int MaxSubArray(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return int.MinValue;

        }

        int max = int.MinValue;

        int currSum = 0;

        int maxSum = int.MinValue;

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

        {

            if (max < nums[i])

            {

                max = nums[i];

            }

            currSum += nums[i];

            if (currSum < 0)

            {

                currSum = 0;

            }

            else

            {

                maxSum = Math.Max(currSum, maxSum);

            }

        }

        return max < 0 ? max : maxSum;

    }

Complexity: O(n)