LeetCode 알고리즘 풀이

브루트 포스로 계산하면 이중 for문으로 인해 O(n^2)으로 시간 초과가 발생하기 때문에 O(n)의 방법으로 풀어야 하는 문제. DP 방법 중 하나이며 최대 부분합을 구하는 카데인 알고리즘을 이용한다.

Hash table에 각 원소를 저장하고 이미 저장된 원소가 다시 불리면 True를 반환하고, 끝까지 순회를 마쳤다면 중복되는 원소가 없기 때문에 False를 반환한다.

전체 곱에서 자기 자신을 나누는 방법을 쓰지 않고, 자신을 제외한 나머지 요소의 곱셈 결과를 출력해야 한다.O(n)의 방법으로 풀어야 하기 때문에, DP의 방법인 누적 배열을 만들어서 해결한다.

가장 큰 부분합을 구하는 DP 문제. DP 개념을 이용하여 이전 배열까지의 최대합을 저장하고 현재 값과 비교하여 최대 값을 갱신해나가면 된다.