백준 BOJ 10211 - Maximum Subarray

부분합 배열 만들어서 해결했다.

부분합 배열을 만들지 않는 O(T*N^3) 풀이로도 풀 수 있다고 한다.

내가 구현한 코드의 시간복잡도는 O(T*N^2)

 

https://www.acmicpc.net/problem/10211

10211번: Maximum Subarray

부분합 배열을 미리 계산해놓고 답을 구하는데,

이때 sum[e] - sum[s] 를 통해 값을 구할 때

e와 s가 같아지는, 즉 아무것도 더하지 않아서 subarray의 길이가 0이 되는 경우는

포함시키면 안되니 이부분만 좀 신경을 써주면 되지 싶다.

 

#include <bits/stdc++.h>
using namespace std;

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int T;
	cin >> T;
	while(T--){
		int N;
		int ans = -998244353;
		int arr[1234] = {0};
		int sum[1234] = {0};
		
		cin >> N;
		for(int i=1; i<=N; i++){
			cin >> arr[i];
			sum[i] = arr[i]+sum[i-1];
		}
		
		for(int i=0; i<=N; i++){
			for(int j=i+1; j<=N; j++){
				ans = max(ans, sum[j]-sum[i]);
			}
		}
		
		cout << ans << "\n";
	}
	
	return 0;
}