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);
}
결과 역시 의도한 대로 나왔음을 알 수 있다
'Programming > 생각해보기' 카테고리의 다른 글
어떻게 해야 null을 입력하면 루프가 종료 될까 (0) | 2021.09.30 |
---|---|
소수 출력 (0) | 2021.04.25 |
배열요소 한 칸씩 뒤로 밀기 (0) | 2021.04.25 |