최대값 구하기

n개의 정수를 입력받아 배열 요소에 저장했을 때, 0 이상의 연속된 정수들의 합 중에서 최댓값을 구하려면 어떻게 해야 할까?

 

-2

1

5

예를 들어서 이러한 배열이 존재한다고 가정할 때, 연속된 정수들의 합을 구하면

 

1) -2 + 1 + 5 = 5

 

2) 1 + 5 = 6

 

두 가지 경우의 수를 가지며, 최댓값은 6이라고 할 수 있다.

 

 1번의 경우는 배열의 0번 인덱스부터 2번 인덱스까지 차례로 더한 것이고

2번의 경우는 배열의 1번 인덱스부터, 2번 인덱스까지 차례로 더한 것이다.

 

이를 간단히 의사 코드로 나타내면

max is zero
for i = 0 to n-2
	sum is zero
    for j = i+1 to n-1
    	sum += data[j]
        if sum > max
        	then max = sum

    

정도로 나타낼 수 있을 것이다.

 

실제 자바 코드로 옮겨본다면

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 < data.length; i++)
			data[i] = kb.nextInt();
		kb.close();
		
		int max = 0;
		for (int i = 0; i < data.length-1; i++) {
			int sum = 0;
			for (int j = i; j < data.length; j++) {
				sum += data[j];
				if(sum > max)
					max = sum;
			}
		}
		
		System.out.println(max);
	}

 

결과 역시 의도한 대로 나왔음을 알 수 있다