[알고리즘]배열의 이어지는 인터벌 최대합 구하기

---

---

# 문제

정수 배열(int array)가 주어지면 가장 큰 이어지는 원소들의 합을 구하시오. 

(단, 시간복잡도는 O(n))

<예제>

Input: [-1, 3, -1, 5]

Output: 7 // 3 + (-1) + 5

Input: [-5, -3, -1]

Output: -1 // -1

Input: [2, 4, -2, -3, 8]

Output: 9 // 2 + 4 + (-2) + (-3) + 8

-------------------

해당 문제는 마이크로소프트 코딩 테스트이다.

문제는 간단하다. 그저 이어지는 배열의 가장 큰 합을 구하면 된다.

시간 복잡도가 O(n)이기 때문에 반복문 한번만에 풀어야하는데

이게 꽤 골치가 아팠다.

머리를 싸매며 풀어봤지만, 나는 결국 이 문제를 풀지 못했다.

다른 사람들의 해답을 보니 간단했었는데...

너무 어렵게 생각을 한 탓인건가...?

# 코드

public class HelloAlgorithm {
    public int Solution(int[] arr){
        int currentSum = arr[0];    // 커서의 역활을 한다.
        int max = arr[0];            // 합을 저장하는 스토리지
 
        for(int i = 1; i < arr.length; i++){
            // 커서가 가리키는 값의 합과 기존의 값의 최대값을 구한다.
            currentSum = Math.max(currentSum + arr[i], arr[i]);
            //currentSum과 현재 최대값의 비교
            max = Math.max(currentSum, max);
        }
        
        // 결과 리턴
        return max;
    }
 
    public static void main(String[] args){
        HelloAlgorithm TempClass = new HelloAlgorithm();
        int[] arr =  {-5, -3, -1};
        System.out.println(TempClass.Solution(arr));
    }
}

# 마무리

위 포스트는 제가 직접 제작한 것 입니다.

그렇기 때문에 틀린점이나 설명이 엉성한 점이 존재할 수 있습니다.

만약 틀린점이나 설명이 엉성한 부분이 존재하면 댓글로 알려주세요.

빠른 처리 하도록 하겠습니다.

티스토리 앱으로는 댓글 이용이 불가능 하므로 웹 브라우저로 봐 주세요

(URL : http://junprogramer.tistory.com/)

읽어주셔서 감사합니다.