[매일프로그래밍] 코딩테스트 07/08/2019

문제

정수 배열(int array)가 주어지면 가장 큰 이어지는 원소들의 합을 구하시오. 단, 시간복잡도는 O(n).

Given an integer array, find the largest consecutive sum of elements.

예제}

Input: [-1, 3, -1, 5]

Output: 7 // 3 + (-1) + 5

Input: [-5, -3, -1]

Output: -1 // -1

Input: [2, 4, -2, -3, 8]

Output: 9 // 2 + 4 + (-2) + (-3) + 8

내가 생각해본 풀이과정

1.규칙

• 시간 복잡도는 O(n)입니다.
• 더해지는 원소는 반드시 인덱스가 이어져 있어야 합니다. (arr[i] + arr[i+3] 같은 경우는 X)

2.순서

시간복잡도가 O(n)이니 2중 for문은 고려하지 않습니다.

배열의 총 합계값으로 초기화한 answer변수와, 인덱스 i번째부터 n-1번째까지의 합이 있을때

두 값을 비교하여 큰 값을 answer에 넣습니다.

배열의 길이만큼(n) 이 작업을 반복한 후 리턴합니다.

3.코드(시간복잡도 O(n)?)

int solution(list<int> arr){
    int *memo = new int[arr.size() + 1];
    int answer = 0, sum = 0;
    list<int>::iterator it;
    for (it = arr.begin(); it != arr.end(); it++) sum += *it;
    while (!arr.empty()) {
        answer = max((sum -= arr.front()), answer);
        arr.pop_front();
    }
    delete[] memo;
    return answer;
}

해설과 정답코드

1.해설

이 문제는 두개의 정수 변수로 현재의 합(currentSum) 과 전체의 제일 큰 합(max Sum)을 저장해야 합니다.

각 원소마다 (currentSum + 원소) 값을 원소 값이랑 비교하고, 더 큰 값이 currentSum이 됩니다.

maxSum은 currentSum 이 바뀔때마다 체크하여 제일 큰 값을 저장하면 됩니다.

2.코드(시간 복잡도: O(n) , 공간 복잡도: O(1))

int solution(int[] arr) {
  int maxSum = arr[0];
  int currentSum = arr[0];
  for(int i = 1; i < arr.length; i++) {
    currentSum = Math.max(currentSum + arr[i], arr[i]);
    maxSum = Math.max(currentSum, maxSum);
  }
  return maxSum;
}