[JAVA] 배열에 연속된 정수들의 합 중 최대값을 구하는 프로그램

Q/

n개의 정수를 입력받아 배열에 저장한다. 이 중에서 0개 이상의 연속된 정수들을 더하여 얻을 수 있는 
최대값을 출력하는 프로그램을 만들어라 

 

 

A/

public class code12 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] data = new int[n];
		
		for(int i=0;i<n;i++)
			data[i] = sc.nextInt();
		sc.close();
		
		int max = 0;
		
		for(int i=0;i<n;i++) {
			for (int j=1;j<n;j++) {
				int sum= 0;
				for(int k=1;k<=j;k++)
					sum +=data[k];
				if(sum>max)
					max=sum;
				
			}
		}
		

	}

}

(시작점 i, 끝점 j. 구간의 합을 sum, 구간의 최대값을 max라 한다.)

 

위 방법이 틀린 건 아니지만 효율이 떨어진다. 다음과 같은 배열이 있다고 생각해보자.

구간의 시작점과 끝점을 생각해보면, j가 배열의  끝까지 도달하면 i가 증가한다.

i를 검사하는 과정이 중복되기 때문에 j를 그냥 끝에 더해주면 i에서 j까지 합을 구할 수 있다. 

 

2

1

-11

7

8

2

9

0

 

				
	for(int i=0;i<n;i++) {
	int sum= 0;
	for(int j=1;j<n;j++)
	sum +=data[j];
	if(sum>max)
	max=sum;
    }