Maximum Sum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Input Format

First parameter - Size of array n
Second parameter - Integer array arr

Output Format

Return the number

Example 1:

Input:
    9
    -2 1 -3 4 -1 2 1 -5 4
Output:
     6
Explanation:
    4 -1 2 1 has the largest sum = 6.

Example 2:

Input:
     1
     1
Output:
     1

Example 3:

Input:
     5
     5 4 -1 7 8   
Output:
     23

Constraints:

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴
• Expected Time Complexity: O(n)
• Expected Space Complexity: O(1)