이런 흡사한 문제를 또 풀고싶다면,

Level3 스티커모으기2 , Level4 도둑질 문제를 풀어보시길 바랍니다.

문제에서 보이는대로 접근을하면,
구간을 모두 탐색하려면 2차 반복문을 작성하는게 편하겟지만,
제한사항이 매우 크고, 중복연산이 많이 실행되어서 당연히 통과하기 힘듭니다.

1. 첫 시작을 -1를 곱할지 , 그대로 가져갈지

첫 시작을 -1로 곱한것과 , 그대로 시작하는 결과는 매우 달라져서
둘의 경우를 분리하여 보셔야합니다.

dp를 2개를 생성해야 한다는 말이죠.

2 . dp 작성
dp 기준을 잡는게 제일 중요한데, dp[n] = n까지 탐색한 모든 부분수열중 최댓값으로 잡습니다.

예시
{2,3,-6,1}

dp[0] 를 음수로 시작을 해보자면, dp[0] = -2 입니다.
dp[1]은 여기서 2가지 선택지가 있습니다. 0번째 숫자를 그대로 가져올지, 또는 지금부터 다시 시작할지,
우린 이 2가지 선택지를 모두 판별해야 하기때문에 다음과 같은 수식이 나옵니다.

dp[1] = Max(dp[0]+두번째숫자, 두번째숫자)

그리고 dp[2] 같은경우는 음수로 시작했으니,
dp[2] = Max(dp[1]+세번째숫자 * -1, 세번째숫자 * -1)이 성립합니다.

즉, 점화식은 dp[n] = Max(dp[n-1]+n번째숫자(n값의 따른 음수 또는 양수), n번째숫자(n값의 따른 음수 또는 양수))
이게 성립이됩니다.

서두에서 말씀햇듯이, 음수로 시작과 양수로 시작한것이 다르므로,

두 dp중 최대값이나오는 값을 반환 하시면 정답이 나옵니다.