[개념공부]Kadane's Algorithm
📒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를 선택해야할 때 많이 사용한다.
Author And Source
이 문제에 관하여([개념공부]Kadane's Algorithm), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@gomhyeok/개념공부Kadanes-Algorithm
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
각 수를 더했을 때 가장 큰 수가 나오는 연속된 부분을 찾는 알고리즘
Dynamic Programming의 일종으로 수열 Algorithm의 기초다.
연속된 최대합을 구하는데 많이 사용된다.
#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를 선택해야할 때 많이 사용한다.
Author And Source
이 문제에 관하여([개념공부]Kadane's Algorithm), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gomhyeok/개념공부Kadanes-Algorithm저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)