23.1) 문제 이해
가장 큰 부분배열의 합의 문제 및 목표
- 주어진 배열에서 가장 큰 연속된 부분배열의 합을 찾아야 합니다.
가장 큰 부분배열의 합의 조건
- 예를 들어, [-2, 1, -3, 4, -1, 2, 1, -5, 4]라는 배열이 주어졌을 때 모든 원소를 더한다면 합은 1이 됩니다.
- 많은 원소를 더한다고 합이 크지는 않습니다. 하지만 가장 큰 연속된 부분배열의 합을 찾는다면 4 + (-1) + 2 + 1 = 6이 됩니다.
- 만약 배열의 원소가 모두 0보다 크 양수라면 가장 큰 부분배열의 합을 찾기 굉장히 쉽습니다.
- 혹은 배열의 원소가 모두 음수라면, 이때는 빈배열([])이 가장 큰 합을 갖는 부분배열이 되고 함수는 0을 반환하게 됩니다.
23.2) 해결 방법
- ① 입력된 배열 arr의 모든 부분 배열의 합의 경우의 수를 찾아 더합니다.
- ② 그리고 모든 경우의 수를 더할 때마다 값들을 새로운 배열에 넣습니다. 이 때, 더해진 값이 음수이면 새로운 배열에 넣지 않습니다.
- ③ 모든 경우의 수의 연산이 끝나면 오름차순으로 정렬합니다.
- ④ 정렬된 배열 안에 값들이 들어있다면, 배열의 마지막 인덱스의 값을 return합니다.
23.3) 코드 구현
- 변수 sum = 0으로 초기화시키고 빈 배열 temp를 선언합니다.
- 만약 입력된 배열 arr이 빈 배열이면 더 이상 진행할 것 없이 0을 return합니다.
- 배열 arr의 모든 부분배열 합의 경우의 수를 구하기 위해 이중 for문을 사용합니다. 이중 for문 중간에 sum = 0으로 다시 초기화시키는 이유는 arr배열의 첫 번째 인덱스에서 모든 경우의 수를 구하는 것이 끝난 후 다음 인덱스에서 모든 경우의 수를 구하기위해 초기화시킵니다.
- 모든 경우의 수를 구해 더하고 temp 배열에 넣으며 진행되는 과정은 위 그림과 같습니다. 단, 더했을 때 음수인 경우는 구하지 않아도 되는 값이므로 temp 배열에 넣지 않습니다.
- for문이 종료되어 temp 배열이 완성되면 selection sorting 방법을 이용하여 temp 배열을 오름차순으로 정렬합니다.
- 만약 temp 배열이 빈 배열이었다면 0을 return하지만 값이 있었다면 가장 마지막 인덱스의 값이 제일 큰 부분배열의 합이므로 마지막 인덱스 값을 return합니다.
23.4) 결과 분석
- 주어진 테스트 환경에서 모두 Pass 하였습니다.
