The Maximum Subarray

사이트: HackerRank
난이도: 미디움
분류: Dynamic programming

문제

정수로 이루어진 배열이 주어질 때, 해당 배열의 subarray가 가진 원소들의 합이 최대인 값과, subsequence가 가진 원소들의 합이 최대인 값을 찾아서 반환하라.

arr = [-1, 2, 3, -4, 5, 10];

// 원소의 합이 최대가 되는 subarray
sum([2, 3, -4, 5, 10]) = 16
// 원소의 합이 최대가 되는 subsequence
sum([2, 3, 5, 10]) = 20

1. 나의 풀이

시간복잡도의 제한을 해결하지 못해서 다른 사람의 코드를 찾아보게 되었다.

function maxSubarray(arr) {
    // Write your code here
    const dp = [];
    const len = arr.length;

    let minus = 0,
        max1 = -10001,
        max2 = 0;

    for (let i = 0; i < len; i++) {
        if (arr[i] < 0) {
            minus += arr[i];
        }

        dp[i] = (dp[i - 1] || 0) + arr[i];
        max1 = Math.max(max1, arr[i], dp[i]);
    
        for (let j = 0; j < i; j++) {
            max1 = Math.max(max1, dp[i] - dp[j]);
        }
    }

    max2 = dp[len - 1] - minus;
    return [max1, max2 === 0 ? max1 : max2];
}

2. 다른사람의 풀이

아래 로직을 보면 각 subarray와 subsequence의 합을 비교하는 로직이 작성되어있다. 해당 로직은 잘 기억해 두었다가 필요할 때 써먹어야겠다.

function maxSubarray(arr) {
    // Write your code here
    let maxSA = arr[0]; // max sub array
    let maxSS = arr[0]; // max sub sequences
    let max = arr[0];

    for (let i = 1; i < arr.length; i++) {
        max = Math.max(max + arr[i], arr[i]);
        maxSA = Math.max(maxSA, max);
        maxSS = Math.max(
            Math.max(maxSS, arr[i]), 
            maxSS + arr[i]
        );
    }
    
    return [maxSA, maxSS];
}