[BOJ] 1912_연속합

연속합

문제 링크: https://www.acmicpc.net/problem/1912

1912번: 연속합

성공

 

결국 O(n)까지 줄였다.
현재 값을 더하는게 이득인지 아닌지만 판단한다.
현재 값을 더했을 때 음의 값을 가질 경우 득이 아닌 실이므로 더하지 않고 더했던 값들을 초기화한다.
득일 경우 계속해서 다음의 값을 더해나간다.
그리고 지금까지의 최대 값을 출력한다.

 

• 정답 코드

    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define maxNum 100001
  
    int list[maxNum];
    int n;
  
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL); cout.tie(NULL);
        cin >> n;
  
        int maximum = -10000;
  
        for (int i = 1; i <= n; i++) {
            cin >> list[i];
            maximum = max(maximum, list[i]);
        }
  
        int sum = 0;
        bool flag = false;
        for (int i = 1; i <= n; i++) {
            if (sum + list[i] < 0) {
                sum = 0;
            }
            else {
                flag = true;
                sum += list[i];
            }
            maximum = max(maximum, sum);
        }
        if(flag)
            cout << maximum;
        else {
            sort(list + 1, list + n + 1);
            cout << list[n];
        }
  
        return 0;
    }

1차 시도 실패

 

무작정 더한다.
하나의 항목부터 n개의 항목까지 그룹핑하여 최대값을 찾는다.
Time Complexity는 O(n^3)이다.

시간 초과.

 

• 미해결 코드

    #include<iostream>
    #include<vector>
    using namespace std;
    #define max(a, b) (a>b ? a : b)
    int list[100000];
    int maximum = -10000;
    int n;
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL); cout.tie(NULL);    
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> list[i];
            maximum = max(maximum, list[i]);
        }
        for (int s = 2; s <= n; s++) {
            for (int k = 0; k < n; k++) {
                int sum = 0;
                for (int t = k; t < k+s; t++) {
                    if (t >= n)
                        break;
                    sum += list[t];
                }
                maximum = max(maximum, sum);
            }
        }
        cout << maximum;
        return 0;
    }

  2차 시도 실패

 

이를 위해 예제들을 각 합을 구해보았다.

 

다음의 규칙을 찾았다.

현재 값 = 자신의 위의 값 + 입력받은 리스트 (현재의 y값) 번째 값

어차피 최대 값을 구하기 때문에 바로 직전의 값을 저장할 필요가 없다.
따라서, 현재 값에 덮어씌운다.
list[2][k] += (list[1][i]);

Time Complexity는 O(n^2)이다.

시간 초과.

 

• 미해결 코드

    #include<iostream>
    #include<vector>
    using namespace std;
    #define maxNum 100001
    #define max(a, b) (a>b ? a : b)
  
    int list[3][maxNum];
    int n;
    int maximum = -10000;
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL); cout.tie(NULL);
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> list[1][i];
            maximum = max(maximum, list[1][i]);
            list[2][i-1] = (list[1][i-1] + list[1][i]);
            maximum = max(maximum, list[2][i-1]);
        }
  
        for (int i = 2; i <= n; i++) {
            for (int k = 1; k <= n - i + 1; k++) {
                list[2][k] += (list[1][i]);
                maximum = max(maximum, list[2][k]);
            }
        }
        cout << maximum;
  
        return 0;
    }