[LeetCode] 53. Maximum Subarray

https://leetcode.com/

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

 

Code :

var maxSubArray = function(nums) {
    // 최대 부분 배열의 합을 저장할 변수를 선언합니다.
    let maxSum = nums[0];
    // 현재까지의 부분 배열의 합을 저장할 변수를 선언합니다.
    let currentSum = nums[0];
    // 배열의 두 번째 요소부터 순회하면서 최대 부분 배열의 합을 찾습니다.
    for (let i = 1; i < nums.length; i++) {
        // 현재 요소를 현재까지의 부분 배열의 합에 더합니다.
        // 다만, 현재 요소 자체가 더 큰 경우에는 현재 요소부터 새로운 부분 배열을 시작합니다.
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        // 최대 부분 배열의 합을 갱신합니다.
        maxSum = Math.max(maxSum, currentSum);
    }
    // 최대 부분 배열의 합을 반환합니다.
    return maxSum;
};

 

Solutions Code :

var maxSubArray = function(nums) {
    // 최대 서브어레이 합을 저장하는 변수
    let max = -Infinity;
    // 현재까지의 부분 합을 저장하는 변수
    let meh = 0;
    // 배열을 순회하면서 최대 서브어레이 합 계산
    for (let i = 0; i < nums.length; i++) {
        // 현재 숫자를 부분 합에 추가
        meh += nums[i];
        // 현재까지의 부분 합이 최대 합을 초과하면 최대 합 갱신
        if (meh > max) {
            max = meh;
        }
        // 만약 현재까지의 부분 합이 음수가 되면 0으로 초기화
        if (meh < 0) {
            meh = 0;
        }
    }
    // 최대 서브어레이 합 반환
    return max;
};

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode