Maximum Subarray solution using TypeScript

This post outlines my TypeScript solution to the "Maximum Subarray" question on LeetCode using a greedy algorithm.

Algorithm: The solution finds the subarray with the largest sum by iterating over each number in the array. For each number it will do the following:

• Set the current sum to be whichever is larger:
  • The current number + current sum
  • The current number
• Set the max sum to be whichever is larger:
  • The current sum
  • The current max sum

Once all the elements have been iterated over, the max sum will be returned.

Time Complexity: Because each element in the array will be visited once, the time complexity it O(n) where n represents the number of elements in the array.

Space Complexity: Because the solution will use a constant amount of space, the space complexity is O(1).

/**
 * Maximum Subarray
 * Given an integer array nums, find the contiguous 
 * subarray (containing at least one number) 
 * which has the largest sum and return its sum.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 *
 * maxSubArray([1, 2, 2, -2, 2]) // 5
 * maxSubArray([1, 5, -7, 4, 2, 1]) // 7
 */
function maxSubArray(nums: number[]): number {
    let sum = nums[0]; // current sum
    let max = nums[0]; // max sum
    let ptr = 1; // pointer
    
    while(ptr < nums.length) {
        sum = Math.max(nums[ptr], sum + nums[ptr]);
        max = Math.max(max, sum);
        ptr += 1;
    }

    return max;
}