---
tags: LeetCode
disqus: HackMD
---

# 53. Maximum Subarray

## Problem link

[Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)

## Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
solution for the `maximum subarray sum`

## Approach
<!-- Describe your approach to solving the problem. -->
When sum is greater than max, assign sum to max and temporarily store the maximum value. When sum is less than 0, it will start to accumulate again from 0, and max must be the maximum value of the subarray at the end of the loop.

## Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$O(n)$$
because the code only traverses each element in the array once
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(1)$$
because the code only uses a constant amount of variables, and therefore does not require additional space.

## Code

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let max = nums[0];
    let sum = 0;
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (sum > max) {
            max = sum;
        }
        if (sum < 0) {
            sum = 0;
        }
    }
    return max;
};