non-verified/MaximumSubarray.cpp

View this file on GitHub
Last update: 2020-08-14 03:16:18+09:00

Code

template<class T> vector<T> MaximumSubarray(const vector<T>& vec, T unit=0) {
	assert(!vec.empty());
	vector<T> dp(vec.size());
	dp[0] = max(vec[0],unit);
	for(int i = 1; i < vec.size(); ++i) dp[i] = max(dp[i-1]+vec[i],unit);
	return dp;
}

#line 1 "non-verified/MaximumSubarray.cpp"
template<class T> vector<T> MaximumSubarray(const vector<T>& vec, T unit=0) {
	assert(!vec.empty());
	vector<T> dp(vec.size());
	dp[0] = max(vec[0],unit);
	for(int i = 1; i < vec.size(); ++i) dp[i] = max(dp[i-1]+vec[i],unit);
	return dp;
}