나열되는 연속합들의 최대합구하기

안녕하세요 jsieun입니다.

제가 백준 1912번문제를 자바로 했던 기억이 있는데 그것을 그대로 C++ 로해서

포스팅을 해보겠습니다. :D

차근차근 C++를 시작하는것이 가장 좋을듯 하여 그렇습니다.

연속되는 숫자들의 합중 최대합이란,

예를 들면

-59

-33

34

0

69

24

-22

58

62

-36

10개의 배열중 이렇게 숫자들이 나열되어 있으면

최대합은 위에 빨간색으로 칠한 부분이 되겠습니다.

즉, 저 숫자들을 다합치면 225 라는 숫자가 나오는데 이 숫자는

저 나열된 숫자중 연속적으로 더했을때 가장 최대로 나오는 숫자의 합입니다.

출력 화면을 보도록 하겠습니다.

다음으로 소스를 보도록 하겠습니다.

#include <stdio.h>
#include <stdlib.h>

static int _ComparArr[10] = { 0 };

bool _MaxSum(int _Arr[]) {
 
 
 _ComparArr[0] = _Arr[0];
 int _Max = _Arr[0];
 for (int i = 1; i < 10; i++)
 {
  _ComparArr[i] = _Arr[i] + _ComparArr[i - 1];
  if(_ComparArr[i] > _Arr[i])
  { }
  else if (_ComparArr[i] < _Arr[i])
  {
   _ComparArr[i] = _Arr[i];
  }
  if (_ComparArr[i] > _Max)
  {
   _Max = _ComparArr[i];
  }
 }
 printf("최대합 : %d\n", _Max);
 return true;
}
void main()
{
 printf("jsieun73.tistory.com\n");
 //배열선언
 int _IntegerArr[10] = { 0 };
 
 //-100~+100랜덤으로 배열에 삽입
 
 for (int i = 0; i < 10; i++)
 {
  _IntegerArr[i] = rand() % 200 - 100;
 }
 for (int i = 0; i < 10; i++)
 {
  printf("나열된 숫자 : \t%d\n", _IntegerArr[i]);
 }
 /*
 int _Integer = 0;
 for (int i = 0; i < 10; i++)
 {
  scanf_s("%d", &_Integer,sizeof(4));
  _IntegerArr[i] = _Integer;
 }
 */
 _MaxSum(_IntegerArr);
}

해석을 하자면,

처음에 _ComparArr 배열 0번쨰 배열에 입력이 된 0번째 배열의 값을 넣습니다.

그리고 _Max 의 값은 입력이 된 0번째 배열의 값을 초기화 해준다음

값을 비교하면서 적절히 _Max 라는 변수가 변경이 됩니다.

자세한 설명은 제 블로그

http://jsieun73.tistory.com/114

여기 들어가시면 나옵니다.

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

감사합니다.