백트레킹
연속 부분 수열구하기
- 슬라이딩, 투포인터, 누적합 가능
- 슬라이딩 윈도우:
- 슬라이딩 윈도우는 일반적으로 고정된 길이의 구간 합을 찾는 데 적합합니다. 연속 부분 수열의 길이가 고정되어 있지 않은 경우에는 윈도우의 크기를 조절할 수 없으므로 이 문제에 적합하지 않습니다.
- 투 포인터:
- 투 포인터는 정렬된 배열에서 특정 목표를 찾거나 구간 내의 특정 조건을 조절하는 데 효과적입니다. 음수와 양수가 섞여 있고 구간의 길이가 자유로운 경우에는, 포인터로 구간을 조절하는 것이 복잡해지고 최적화가 어려워지므로 이 문제에는 적합하지 않습니다.
- 누적합:
- 누적합을 사용해 모든 구간 합을 빠르게 계산할 수는 있지만, 연속 부분 수열을 찾기 위해 모든 시작과 끝을 비교해야 하므로 시간 복잡도가 O(N²)으로 비효율적입니다.
구현
- 메서드로 다 만들자
- 중간에 돌리면서 업데이트하는 거 조심하자 → 바로 업데이트 하면 안된다.
- 자잘한 조건 잘 해결하기