1 번째 시도(2017)

  • MAX_N을 최댓값 + 1로 주어야 하는데 최댓값으로 주었다.
  • dp[i] : 1에서 i번째까지 왔을 때의 최댓값
  • 점화식 
      dp[i] = max(dp[i-1] + input[i], input[i])
  res = max(dp[i]) (1 <= i <= N)

2 번째 시도(2021-02-02)

  • dp[MAX_N][2]
    • dp[i][0] : 1에서부터 시작해 i번째 와서 i번째를 포함하지 않았을 때의 최댓값
    • dp[i][1] : 1에서부터 시작해 i번째 와서 i번째를 포함했을 때의 최댓값
  • 점화식 
      dp[i][0] = max(dp[i-1][0], dp[i-1][1])
  dp[i][1] = max(dp[i][1], dp[i-1][1] + input[i])
	
  res = max(dp[N][0], dp[N][1])