# 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;
}
``````