Codility Lesson9 - MaxSliceSum

🔍 문제

---

주어진 배열안에서 최대 부분합 구하기 문제이다.

MaxSliceSum coding task - Learn to Code - Codility

 

✏️ 풀이 - JS

---

MaxProfit 문제를 풀 때 카데인 알고리즘을 공부했었기 때문에 바로 풀 수 있었다. 시간복잡도는 O(N)이다.

카데인 알고리즘에 대한 포스트 👉 Dynamic Programming - Kadane’s Algorithm (카데인 알고리즘)

function solution(A) {
    if(A.length === 1) return A[0];

    let localMaxSum = A[0];
    let globalMaxSum = A[0];

    for(let i = 1 ; i < A.length; i++) {
        localMaxSum = Math.max(A[i], localMaxSum + A[i]);
        globalMaxSum = Math.max(globalMaxSum, localMaxSum);
    }

    return globalMaxSum
}