백준 10211 Maximum Subarray

문제 링크 : www.acmicpc.net/problem/10211

10211번: Maximum Subarray

문제 요약

-주어진 N개의 길이 배열에서 최대합이 되는 부분 배열을 구하기

 

생각

-N이 1000이하로 작아서 for문 중첩으로 브루트하게 접근해도 되겠지만 N이 큰경우 힘들다.(선형 복잡도로 생각하기)

-DP문제가 익숙하지 않아서 처음엔 투 포인터로 생각해봤지만, 음수와 양수가 섞여있는 배열이기 때문에 s,e증가 조건 설정을 할 수 없다.

-DP로 접근 

 

풀이

-2번인덱스부터 dp 메모이제이션 해 나아간다.

1) 해당 인덱스와 이전부분합을 더한 경우가 더큰 경우

2) 이전부분합을 더하지않고 해당인덱스자체가 더 큰경우

-dp[j]=max(dp[j-1]+arr[j], arr[j]) 

 

후기

-부분합의 배열길이가 일정하지 않은경우, 최대합 최소합 같은경우 dp생각해볼수있다.

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
using namespace std;
int arr[1001];
int T,N;
int dp[1001];
int main(void) {
	scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		scanf("%d", &N);
		memset(dp, 0, sizeof(dp)); // Testcase마다 초기화
		for (int j = 1; j <= N; j++) {
			scanf("%d", &arr[j]);
		}
		
		//dp[1]초기화하고 2부터 dp계산
		dp[1] = arr[1];
		int total = dp[1];
		for (int j = 2; j <= N; j++) {
			dp[j] = max(dp[j - 1]+arr[j], arr[j]);
			total = max(total, dp[j]);
		}
		printf("%d\n", total);
	}
}