[Kickstart][2020][Round E] 1. Longest Arithmetic

문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff47/00000000003bf4ed

Kick Start - Google’s Coding Competitions

---

음수가 아닌 정수형 배열이 주어질 때, 최장 부분산수배열 길이를 구해라. 이때, 부분산수배열의 연속되는 원소의 차이는 서로 같다. ex) [1,3,5], [5,5,5]

---

배열을 처음부터 탐색하면서 이전 원소 차이를 diff 변수(arr[i-1] - arr[i-2])에 저장해둔다. 그리고 부분산수배열의 길이를 변수 cnt에 저장한다.

탐색중인 원소와 이전 원소의 차이(arr[i] - arr[i-1])가 diff 변수와 같다면 부분산수배열이 될 수 있으므로 cnt+1을해준다.

diff 변수와 다르다면 arr[i-1], arr[i] 부터 다시 부분산수배열이 가능한지 체크해가면서 cnt를 구해야 하므로 cnt = 2로 갱신해주고 위 알고리즘을 다시 진행한다. 이 때, 탐색하고 있는 i가 0이라면 arr[i-1]은 존재하지 않으므로 cnt는 1로 갱신한다. 이를 모든 배열을 탐색할 때까지 반복하고 탐색중에 나오는 cnt중 최대값이 정답이 된다.

 

시간복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codejam/kickstart/2020/roundE/Longest%20Arithmetic.cpp