[SW Expert Academy]Professional-3819:최대 부분 배열

배열의 연속합 중 최대를 구하는 문제이다. Dynamic Programming 방식으로 접근해서 풀었다.

 

DP배열을 생성하여 i를 끝으로 하는 부분 합 중 최댓값을 저장하도록 하였다.

즉, DP[i]는 i번째 원소를 포함하는 최대 연속 부분합이다.

따라서 dp 배열의 최댓값을 결과로 리턴하면 된다!

 

참고로

dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);

이렇게 식을 만들었는데 음수값이 아닌 경우만 확인해줘도 되므로

dp[i] = Math.max(dp[i - 1], 0) + arr[i];

이렇게도 가능하다.

 

그나저나 이 문제는 BufferedReader를 사용하면 안되고 Scanner를 사용해야만 메모리 초과가 나지 않는다.

(데이터에 공백이 잘못 설정되었다는 소문이 있습니다...)

 

github.com/SuyeonChoi/Algorithms/blob/master/SW%20Expert%20Academy/Java/DP/p3819.java

SuyeonChoi/Algorithms