[Leetcode] Maximum Subarray(Kadane's Algorithm)

53. Maximum Subarray

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

Example 1:

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.

Example 2:

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

Example 3:

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

Constraints:

1 <= nums.length <= 10``5

-10``4`` <= nums[i] <= 10``4

Follow up: If you have figured out the O(n)solution, try coding another solution using the divide and conquer approach, which is more subtle.

How to appoach?

optimized brute force

function maxSubArray(nums: number[]): number {
    let max_subarray = Number.NEGATIVE_INFINITY;
    for (let i = 0; i < nums.length; i++) {
        let current_subarray = 0;
        for (let j = i; j < nums.length; j++) {
            current_subarray += nums[j];
            max_subarray = Math.max(max_subarray, current_subarray);
        }
    }
    return max_subarray;
}

1. create the smallest number as max value. it can't be 0 since there are negative numbers in nums array.
2. create for loop starting from 0, and set current value as 0.
3. create inner for loop which get the index of outer loop as starting point.
4. and add the nums elements to the current value.
5. so this will check all the value accumulation in nums array.
6. max value will be Math max to compare the initial max value and the current value which accumulated to the j index so far.
7. at the end, return the max value.

summary

this way check all the possible accumulation value from nums array.

T comp will be O n2 since there are two loops iterate all over the nums array.

and S comp will be O 1.

kadane's algorithm

function maxSubArray(nums: number[]): number {
    let currentSubarray: number = nums[0];
    let maxSubarray: number = nums[0];

    for (let i = 1; i < nums.length; i++) {
        let num: number = nums[i];
        currentSubarray = Math.max(num, currentSubarray + num);
        maxSubarray = Math.max(maxSubarray, currentSubarray);
    }

    return maxSubarray;
}

1. initialize two number as current and max which has the nums first element.
2. create for loop starting from index 1, and current will be the comparison of index element or current + index element. Bigger one will be current.
3. it will be continued as current since it's starting newly from the index element or accumulate the elements.
4. and also set max as Math.max to compare the current and the max value and set the bigger one as max.
5. return the max value.

summary

this wouldn't create other spaces other than input so space c will be O1

And time c will be On, since it will check all the elements in nums array.