[해커랭크]Max Array Sum (Dynamic Programming)

배열이 주어지고 배열의 일부 원소 합중 최대가 되는 조합을 찾는다.
이때 인접한 원소는 선택할 수 없다.

ㅇ

 

max_arr배열에 해당 원소 까지의 최대가 되는 합을 계속해서 갱신해 나간다.
모든 원소가 음수일 때는 0을 return 해야하므로, 처음에는 0과 arr[0]중 최대값을 넣는다.
index 1 까지의 최댓값 : arr[0]만 선택할 때 or arr[1]만 선택할 때
index 2 까지의 최댓값 : arr[2]만 선택할 때 or arr[1]만 선택할 때 or arr[0]만 선택할 때 or arr[0] + arr[2]
...

index i 일때 

max(max_arr[i-1],max(max_arr[i-2],max(arr[i], arr[i]+max_arr[i-2])))
ㄴ> max(본인선택하지 않고 이전까지 최대, max(본인선택하지 않고 비인접 index까지 선택했을 시 최대, max(본인도 선택하고 비인접 index 까지 선택시 최대)))

이렇게 계속해서 max_arr를 갱신한 후 최대값을 찾는다.