#쉽게 푸는 알고리즘 #4 나열된 수 연속합 최대값 구하기 #백준1912번

제가 진행중인 프로젝트에서 문제가 발생하여 해결하느라 알고리즘 포스팅이 늦었습니다. :(

이번시간에는 여러개의 숫자가 나열된 숫자를 연속된 몇개의 숫자를 선택해서 구할수 있는 최대합을 구하는 알고리즘이 되겠습니다. 

무슨 말이냐 하면 아래 표처럼 10개의 숫자가 나열되어있습니다.

97

-23

66

55

-17

-100

-60

70

15

-98

이렇게 되어있으면, 연속된 숫자를 선택해서 구할수 있는 최대합은 주황색으로 칠한 부분인 "195" 가 최대합입니다.

우선 설명에 앞서서 소스부터 먼저 보여드리고 해석 하도록 하겠습니다.

import java.util.Scanner;

public class blogClass {

static int _IntegerArr [] = null;

static int _ComparArr[] = null;

public static void main(String[] args) {

// TODO Auto-generated method stub

System.out.println("jsieun73.tistory.com");

System.out.println("숫자 10개를 입력하시오");

_IntegerArr = new int[10];

_ComparArr = new int[10];

Scanner scaner = new Scanner(System.in);

for(int i=0; i< 10; i++)

{

_IntegerArr [i] = scaner.nextInt();

}

_MaxSum();

}

static boolean _MaxSum(){

if(_IntegerArr.length != 10) return false;

_ComparArr[0] = _IntegerArr[0];

int _Max = _IntegerArr[0];

for(int i=1; i< 10; i++)

{

_ComparArr[i] = _IntegerArr[i] + _ComparArr[i-1];

if(_ComparArr[i] > _IntegerArr[i])

{

}

else if(_ComparArr[i] < _IntegerArr[i])

{

_ComparArr[i] = _IntegerArr[i];

}

if(_ComparArr[i] > _Max)

{

_Max = _ComparArr[i];

}

}

System.out.println("값 : " + _Max);

return true;

}

}

그리고 출력화면을 보여드리도록 하겠습니다.

우선 조건은 숫자 10개를 입력한다는 가정하에 배열을 만들어보았습니다. 

(숫자 임의의 숫자로 바꾸고싶다면 배열을 New 한부분을 Scanner 로 이용하여 크기를 지정하고, MaxSum 메소드

반복문에도 그에 맞게 설정하시면 됩니다.)

혹시몰라서 이것도 올려드립니다. 

import java.util.Scanner;

public class blogClass {

static int _IntegerArr [] = null;

static int _ComparArr[] = null;

static int _Count = 0;

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner scaner = new Scanner(System.in);

System.out.println("jsieun73.tistory.com");

System.out.println("몇개의 숫자를 입력할것인가요? ");

_Count = scaner.nextInt();

_IntegerArr = new int[_Count];

_ComparArr = new int[_Count];

System.out.println("숫자를 입력하시오 ");

for(int i=0; i< _Count; i++)

{

_IntegerArr [i] = scaner.nextInt();

}

_MaxSum();

}

static boolean _MaxSum(){

if(_IntegerArr.length != _Count) return false;

_ComparArr[0] = _IntegerArr[0];

int _Max = _IntegerArr[0];

for(int i=1; i< _Count; i++)

{

_ComparArr[i] = _IntegerArr[i] + _ComparArr[i-1];

if(_ComparArr[i] > _IntegerArr[i])

{

}

else if(_ComparArr[i] < _IntegerArr[i])

{

_ComparArr[i] = _IntegerArr[i];

}

if(_ComparArr[i] > _Max)

{

_Max = _ComparArr[i];

}

}

System.out.println("값 : " + _Max);

return true;

}

}

이 알고리즘에 대해서 간단히 설명하도록 하겠습니다. 

//배열의 크기는 10개로 지정한다는 가정하에 입니다.

_IntegerArr 라는 배열안에는 아래와 같이 숫자가 입력됩니다.

97

-23

66

55

-17

-100

-60

70

15

-98

소스 하나하나에 대해서 설명을 해보도록 하겠습니다.

참고 

Arr = _IntegerArr[]

Comp = _ComparArr[]

Max = _Max

#Main 함수 

여기는 값을 입력하고 배열의 크기를 정하는 부분이므로 패스 하도록 하겠습니다.

#_MaxSum 메소드

_IntegerArr.length != _Count return false;

혹시나 값을 입력하는 과정에서 배열의 크기가 잘못된경우 제대로된 값이 안나올수있으니 함수종료.

_ComparArr[0] = _IntegerArr[0];

int _Max = _IntegerArr[0];

처음에 Comp 배열과 Max 변수에 초기값을 Arr 배열의 첫번째 값을 저장해 둡니다.

그후 반복문은 1부터 배열 크기까지 반복하는 반복문이 되겠습니다.

_ComparArr[i] = _IntegerArr[i] + _ComparArr[i-1];

우선 Comp배열의 값을 Arr 배열의 i번째 값과 Comp 배열의 i-1 번쨰 값을 저장합니다. 

// i 가 1일경우에는 Comp 의 값은 -23 + 97 이 되겠습니다.

그후 Comp 배열의 i 번째 값과 Arr 배열의 i 번째 값을 비교합니다.

 if(_ComparArr[i] > _IntegerArr[i])

Comp 배열의 i 번째 값이 Arr i 번째 값보다 클시 그냥 넘어갑니다.

물론 없어도 상관은 없지만, 이해하기 쉽게 하기 위해서 이러한 조건문을 만들었습니다.

else if(_ComparArr[i] < _IntegerArr[i])

여기가 가장 중요합니다. 

Comp 배열의 i 번째 값이 Arr 배열의 i 번째 값보다 작을시,

Comp 배열의 i 번쨰 값은 Arr 배열의 i 번째 값으로 다시 저장하게됩니다.

이유는, Comp 배열의 i 번쨰 값을 초기화 하기 위해서 입니다. 쉽게 말해서 

값이 올라가다가 Arr 배열의 값보다 작을경우 그 누적합의 최대값은 Arr 의 배열의 i 번째값이 되기 때문입니다.

if(_ComparArr[i] > _Max)

마지막으로 Comp 배열의 i 번쨰 값이 최종적으로 Max 변수보다 클경우 Comp 값을 Max 로 다시 변경합니다.

즉, 2번쨰 조건문에서 Arr 의 값이 크고 Max 값보다 크면 그것이 바로 연속합의 최대값이 됩니다.

다소 이해하기 어려울거 같아서 조건문마다 Comp 배열 , Arr 배열 Max 값들의 진행상황을 출력해서 보여드리도록 하겠습니다.

예시 하나 더 추가해서  백준에있던 값들을 입력해보도록 하겠습니다.

이번에는 

-10

-7

5

-7

10

5

-2

17

-25

1

값을 입력해보도록 하겠습니다.

이상 포스팅을 마치도록 하겠습니다.