[코테] 백준 - 연속합(1912)

문제

• 배열 원소의 개수 n 제공
• 배열의 연속된 수에서 가장 큰 합 구할 것

코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n=0;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
    }
    int CurrentMax=v[0];
    int Max=v[0];
    for (int i=1;i<n;i++)
    {
        CurrentMax=max(CurrentMax+v[i],v[i]);
        Max=max(Max,CurrentMax);
    }
    cout<<Max;
    return 0;
}

풀이

• 카데인 알고리즘 이용
• 현재 최대 합(CurrentMax), 전체 최대 합(Max)를 이용하여 구현
• 이전까지의 원소들의 합과 현재 원소를 합한 값과 현재 원소의 값을 비교하여 현재 최대 합 결정
  ㅡ> 현재 원소의 값이 너무나 큰 음수여서 오히려 합이 작아져 다음 원소보다 작아지면 부분 배열의 시작점이 변경
• 전체 최대 합 변수를 이용하여 배열 전체에서의 최대값 추적

 

---

참고자료

https://www.acmicpc.net/problem/1912

https://fubabaz.tistory.com/65

[JAVA] 카데인 알고리즘(Kadane's Algorithm)