LeetCode Maximum Subarray (JavaScript), DP

링크 : https://leetcode.com/problems/maximum-subarray/description/

문제 설명

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 <= 105
• 104 <= nums[i] <= 104

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.

---

문제 풀이

DP를 활용하여 문제 풀이

이전 최대 값을 (현재 값 vs 현재 값 + 이전 최대 값)으로 최신화 시켜가면서 검사

• 이전에 합한 값 + 현재 값이 더 크냐 아니면 더하지 않은 현재 값이 더 크냐를 비교하여 prevMaxValue를 갱신하면 됨

즉, 특정 index까지 최대 합은 prevMaxValue에 저장 됨

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let answer = nums[0];
    let prevMaxValue = nums[0];

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] < prevMaxValue + nums[i]) {
            prevMaxValue = prevMaxValue + nums[i];
        } else {
            prevMaxValue = nums[i];
        }

        answer = Math.max(answer, prevMaxValue);
    }

    return answer;
};

---

결론

DP로 접근하기 위해 nums.length만큼 배열을 만들고 각 index까지의 최대 값을 저장해 나가면서 해결할 수 있음

-> 더 최적화 하는 방안은 굳이 배열을 선언하지 않고도 해결이 가능

-> 비교는 이전 index 값과 비교하기 때문에 값이 1개만 필요 즉, prevMaxValue 변수 하나만 선언하여 이전 index까지의 최대 값을 저장해두면 공간 복잡도를 O(1)로 줄일 수 있음

 

시간 복잡도 : O(n)