알고리즘 << 잘하는사람 구함..

[익명(175.204)]

어떤 n개의 숫자를 가지는 배열이 있다 할 때

해당 배열 내에서 연속된 구간 [a, b]에 대한 합을 S(a, b)라 할 때, S(a, b)의 최대값을 어떻게 구하면 좋을까

dp로 풀 수 있다는데 잘 모르겠음

[익명(220.78)]

유명한 문제임

[익명(175.204)]

잘 모르겠음.. dp[i] = Math.max(arr[i], dp[i-1]+arr[i]) 라는데 이해가 안감

[익명(182.218)]

웰노운 - dc App

[익명(175.117)]

dp[i] 를 a[x]+...+a[i] 의 최댓값이라고 하자. 즉 오른쪽을 i로 고정시켰을 때의 최댓값. 그러면 dp[i+1]은 dp[i]+a[i+1] 이거나 a[i+1] 임. 전자는 이전 최대구간에서 i+1 번째를 추가한거고 후자는 그게 음수이고 a[i+1] 이 큰 양수여서 dp[i] 구간을 택하지 않는게 나을 때임. 즉 저 둘을 max 한 다음에

[익명(175.117)]

dp[i]들의 최댓값을 구하면 됨