동적 계획----배열 의 합 최대 및 곱 하기 최대

//          
int maxSubArray(vector nums){
	if (nums.size() == 0)
		return 0;

	int *dp = new int[nums.size()];
	int r = nums[0];
	dp[0] = nums[0];		//           
	for (int i = 1; i < nums.size(); i++){
		int temp = nums[i];
		dp[i] = max(temp,dp[i-1]+temp);
		r = max(dp[i],r);
	}

	return r;
}

//                     ，                   
int maxProduct(vector nums) {
	if (nums.size() == 0) return 0;
	int* maxValue = new int[nums.size()];
	int* minValue = new int[nums.size()];
	int r = nums[0];
	maxValue[0] = r;
	minValue[0] = r;
	for (int i = 1; i < nums.size(); i++) {
		int n = nums[i];
		int a = maxValue[i - 1] * n;
		int b = minValue[i - 1] * n;
		maxValue[i] = max(n, max(a, b));
		minValue[i] = min(n, min(a, b));
		r = max(maxValue[i], r);
	}
	return r;

}