백준 13398 : 연속합 2

문제 링크 접근 방법 DP(다이나믹 프로그래밍)로 풀이하였다. 수를 제거하지 않았을 때 최대 누적합은 sum[]에, 수를 하나 제거했을 때 최대 누적합을 sumR[]에 저장하고 누적합들 중 최대를 출력하면 된다. sum[i] = Math.max(0, sum[i-1]) + num[i]; 일반 누적값은 이전값에 현재값을 더해준다. 이전값이 음수라면 새로 시작하면 된다. (최대 누적합) sumR[i] = Math.max(sumR[i - 1] + num[i], sum[i - 1]); 수를 제거했을 때는 현재위치를 제거했을 때 값 sum[i-1]과 이전에 제거한 최대를 유지하고 현재를 더한 sumR[i]+num[i] 중 큰 값을 대입해주면 된다. 삽질했던 부분 수를 제거하지 않았을 때 연속되어야 한다는 생각 때문..