[LeetCode] Maximum Subarray (javascript)

문제

 

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

 

---

문제[번역]

정수 숫자열이 주어집니다.

최소 하나의 숫자를 포함한 연속적 최대 합을 구하세요

 

 

---

 

Example 1

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2

Input: nums = [1]
Output: 1

Example 3

Input: nums = [5,4,-1,7,8]
Output: 23

 

 

 

 

---

제약조건

 

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 10

 

---

접근방법

[1, -1, 3, 5]를 예시로 설명하겠습니다.

 

1. 두 번째 값부터 시작(-1)

num[1] = Math.max(num[1], num[0] + num[1]) 중에 큰 것을 골라서 두 번째 인덱스에 넣습니다.

이 과정을 반복합니다.

num[2] = Math.max(num[2], num[2] + num[1])

...

...

...

이처럼 값의 누적을 이용해(dp) 답을 구했습니다.

 

 

 

 

---

코드

 

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    for(let i=1; i<nums.length; i++){
        nums[i] = Math.max(nums[i],nums[i] + nums[i-1]);
    }
    return Math.max(...nums);
};

 

 

---

주의사항

 

x