연속된 정수들을 더하여 얻을 수 있는 최대값

문제

• n개의 정수를 입력받아 배열에 저장한다.

• 이들 중에서 0개 이상의 연속된 정수들을 더하여 얻을 수 있는 최대값을 구하여 출력하시오.

예제 입력

13
-2 3 5 -14 12 3 -9 8 -1 13 2 -5 4

예제 출력

28

풀이

public class Main{
    public static void main(String[] args){
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int[] data = new int[n];
        for(int i=0; i<n; i++)
            data[i] = kb.nextInt();
        kb.close();
        
        int max = 0;
        for(int i=0; i<n; i++){
            int sum = 0;
            for(int j=i; j<n; j++){ // 시작과 끝점이 같음
                sum += data[j];
                if(sum > max)
                    max = sum;
            }
        }
        System.out.println("The max sum is " + max);
    }
}

Reference

• 권오흠 교수, 인프런 - "Java로 배우는 자료구조",www.inflearn.com/course/java-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0/dashboard(2020.09.06)