sw 5642. [Professional] 합

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXQm2SqdxkDFAUo&categoryId=AWXQm2SqdxkDFAUo&categoryType=CODE

SW Expert Academy

 

연속 배열 최대 값은 간단하게 DP로 해결 가능

만약 길이를 찾는 거면 투포인터..

 

그리고 전부 음수일 수 있으니 maxa는 arr[0]으로 초기화 

#include<iostream>
#include <string.h>
#include<string>
#include<queue>
#include <vector>
#include<map>

using namespace std;
int arr[100000];
int D[100000];
int main(int argc, char** argv)
{
	int test_case;
	int T;
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		int N;
		cin >> N;
		memset(arr, 0, sizeof(arr));
		memset(D, 0, sizeof(D));

		for (int i = 0; i < N; i++)
		{
			cin >> arr[i];
		}

		D[0] = arr[0];
		int maxa = 0;
		for (int i = 1; i < N; i++)
		{
			D[i] = max(0, D[i - 1]) + arr[i];
			if (maxa < D[i])
			{
				maxa = D[i];
			}
		}

		cout << "#" << test_case << " " << maxa << endl;

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}