📒Kadame's Algorithm

✍Kadame's Algorithm 이란?

각 수를 더했을 때 가장 큰 수가 나오는 연속된 부분을 찾는 알고리즘
Dynamic Programming의 일종으로 수열 Algorithm의 기초다.
연속된 최대합을 구하는데 많이 사용된다.

✍특징

📌특징

• 시간복잡도가 O(n)이다.
• Dynamic programming의 일부다. -> Memoziation 사용
• 연속된 부분을 찾는다.

📌핵심

• 요소를 하나씩 더해야한다.
• 더한 값을 변수에 저장하고 기억한다.
• 그 값이 마지막 저장보다 크면 변수를 대입한다.

📌구현

#include<iostream>
#include<vector>
#include<algorithm>

int kadane (vector<int> arr){
	int cur=0;
    int big=arr[0];
    
    for(int i=0; i<arr.size(); i++){
    	cur=max(cur+arr[i], arr[i]);
        if(big<cur){
        	big=cur;
        }
    }
    
    return big;
}

현재 인덱스를 i라고 한다면 a~i까지의 합을 유지하거나 i~의 새로운 합을 만들거나를 선택한다.
어떤 연속된 부분 집합이나 array를 선택해야할 때 많이 사용한다.