[leetcode][1186] Maximum Subarray Sum with One Deletion

문제 : https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/

---

DP로 해결했다.

연속되는 subarray의 최대합을 구하는 문제인데, 최대 하나의 요소를 삭제해도 된다고 한다.

이 말은 즉, 연속합 혹은 한 칸 떨어진 2개의 subarray의 합들 중 최대값을 구하는 문제이다.

2개를 구해야하므로 2차원 배열이 필요하다.

dp[0][i] = i번째 요소를 시작기점으로 contiguous max sum.
dp[1][i] = i~끝 범위에서 구한 subarray에서 하나의 요소를 삭제했을 때 max sum.

채워야 되는 배열은 위와 같다.

// now = arr[i]

// 최대값(now, now를 포함하고 (i+1)을 시작점으로 가지는 contiguous max sum
dp[0][i] = max(now, now + dp[0][i+1]) 

/** 최대값(now를 제외한 경우, 
  * now를 포함하고 (i+1)을 시작점으로 가지고 하나의 요소가 삭제된 contiguous max sum) 
  */
dp[1][i] = max(dp[0][i+1], now + dp[1][i+1])

점화식은 위와 같다.

 

시간복잡도는 O(N). N = |arr|

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1186.%20Maximum%20Subarray%20Sum%20with%20One%20Deletion.cpp