카데인 알고리즘

2025. 5. 27 지피티한테 문제를 내달라고 했다.

//문제 3. 최대 연속 합 구하기
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int num;
    int n=0, ans =0;
    while(cin >> num){
        n+=num;
        //입력받은거랑 새로운거를 계속 더해서
        if(n<0) n=0; //합이 음수가 나오면 0으로 초기화하고
        if(n>ans) ans =n; //합이 답보다 크면 그 값으로 답 업데이트하기
    }
    
    /* 다른 방법으로 풀면 <= 얘도 뒤에꺼랑 전반적인 흐름은 똑같음
    vector<int>v;
    while(cin >> num){
        v.push_back(num);
    }
    int sum = 0, ans =0;
    for(int i=1; i<v.size(); ++i){
        if(v[i-1]+v[i] < 0) sum =0;
        else sum += v[i];
        if(sum > ans) ans = sum;
    }*/
    cout << ans;
    return 0;
}

 

"현재까지의 합이 0보다 작으면 버린다"

Kadane's Algorithm의 핵심 아이디어

 

⚠️ 보완해야할 부분 ⚠️

모든 수가 음수일 경우, 가장 큰 음수 하나가 출력되어야하지만

이 코드는 0을 출력한다는 문제가 있다

 

이를 반영해서 수정하면

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int num;
    vector<int>v;
    while(cin >> num){
        v.push_back(num);
    }
    
    int sum =v[0], ans =v[0];
    
    for(int i=1; i<v.size(); ++i){
        sum = max(v[i], sum+v[i]);
        // 반복문 돌면서
        // v[i] 랑 sum에 v[i] 더한거 중 큰 값으로 sum 값 계속 업데이트
        // 더한게 계속 크면 계속 더해가며 업데이트 됨
        ans = max(ans,sum);
        // 더하고 나서는 이제 최대값 계속 비교해가면서 저장
    }
    cout << ans;
    return 0;
}