[SwExpertAcademy] 최대 부분 배열

문제 출처 :

https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWWxo6c6AVkDFAW4

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

잘 알려진 문제이다.

dp의 i번째 값은 i - 1번째까지 누적된 값과 현재 arr[i] 값을 더하는데 이때 음수가 되면 0으로 처리해주고 

그게 아니라면 계속해서 더해준다.

그렇게 얻어진 값들중 최댓값이 문제의 답이 된다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

#include <iostream> #define max(a, b)(a > b ? a : b)   int arr[200002]; int dp[200002];   int main() {     int tCase;     scanf("%d", &tCase);       for (int tc = 1; tc <= tCase; tc++) {         int n;         scanf("%d", &n);           for (int i = 0; i < n; i++) {             scanf("%d", &arr[i]);             dp[i] = 0;         }           int ans = max(arr[0], 0);         dp[0] = max(arr[0], 0);         for (int i = 1; i < n; i++) {             dp[i] = max(0, dp[i - 1] + arr[i]);             ans = max(ans, dp[i]);         }           printf("#%d %d\n", tc, ans);       }     return 0; } Colored by Color Scripter

cs