水题

• • 教训：
  • 前缀和思想求解
  • DP动态规划

教训：

 对于复杂的参数不要使用宏定义函数，尤其是函数嵌套使用时，函数涉及++、- -之类的。

前缀和思想求解

#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
	int n,l=0;
	while (cin >> n)
	{
		l++;
		int arr[18];
		ll f[18][18] = {};
		for (int i = 0; i < n; i++)
			cin >> arr[i];
		f[0][0] = arr[0];
		int max = 0;
		for (int i = 1; i < n; i++)
		{
			f[0][i] = f[0][i - 1] * arr[i];
			if (f[0][i] > max)max = f[0][i];
		}
		for (int i = 1; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (i > j)continue;
				f[i][j] = f[0][j] / f[0][i - 1];
				if (f[i][j] > max)max = f[i][j];
			}
		}
		cout <<"Case #"<<l<<": The maximum product is "<< max <<"."<< endl;
	}
	return 0;
}

时间复杂度是O(n^2)

DP动态规划

 如果直接写固定终点类的状态（如dp(i)表示以i结尾的连续序列的最大乘积），则不能求解，因为问题不满足最优化原理。即过程最优解可得到这一策略的最优解，比如2 5 -1 -2,2*5=10,就会不会乘以-1才是阶段三的最好决策，而在阶段四时10更不会选择乘以-2变成负数，所以明显解为10而非20。

 那么如何使用动态规划求解呢？很简单，解决问题就好了！问题在于某一个状态为负值，但它可能涉及以后的其他状态的决策（比如25-1就应该涉及第四阶段是否*2的决策），所以我们尝试使用另一个dp数组记录最小值，当在一个状态做决策时也要比较最小值的情况。

考虑状态有两种:
 第一种dpMax(i)表示步步选择最好决策(从第二步开始)时i阶段所形成的情况。
 第二种dpMin(i)表示步步选择最差决策(从第二步开始)时i阶段所形成的情况。

考虑状态：
 dpMax(0)=arr[0];
 dpMin(0)=arr[0];
 dpMax[i]=Max(dpMax[i-1]*a[i],a[i],dpMin[i-1]*a[i]);
 dpMin[i]=Min(dpMin[i-1]*a[i],a[i],dpMax[i-1]*a[i]);

题解代码(含注释)

#include<iostream>
int Max(int a, int b)//在复杂时使用宏定义函数会出错，比如++或者嵌套调用宏定义
{
	return a > b ? a : b;
}
int Min(int a, int b)//切记在复杂参数时不要使用宏定义！！
{
	return a < b ? a : b;
}
using namespace std;
int dp[18];//存储最好情况
int dpMin[18];//存储最坏情况
int main()
{
	int n,i=0;
	while (cin >> n)//输入序列元素个数
	{
		i++;//记录第几个样例
		int arr[18];
		for (int i = 0; i < n; i++)//输入序列
			cin >> arr[i];
		int max = arr[0]; //要将max初始化为arr[0]也即dp[0]（不初始化为方便的0也因为是这个原因）
		dp[0] = arr[0];	  //初始化状态
		dpMin[0] = arr[0];//初始化状态
		for (int i = 1; i < n; i++)//从1开始状态转移！（转移过程中的状态会和max比较,但没有状态0,所以一定要将Max初始化为状态0）
		{
			dpMin[i] = Min(Min(arr[i], arr[i] * dpMin[i - 1]), arr[i] * dp[i - 1]);//状态转移
			//if (i == n-1)cout << arr[i] << " " << arr[i] * dpMin[i - 1] << " " << arr[i] * dp[i - 1] << endl;
			dp[i] = Max(Max(arr[i], arr[i] * dpMin[i - 1]), arr[i] * dp[i - 1]);  //状态转移
			if (dp[i] > max)max = dp[i];//比较更新max（所有dp的情况的最大那一种就是最优解）
		}
		cout << "Case #"<<i<<": The maximum product is " << (max>0?max:0)<< "." << endl;//输入（max如果小于0要输出0）
	}
	return 0;
}