力扣-152-乘积最大的子数组

对于dp[i]，

• 如果nums[i-1]>0，dp[i-1]也>0，那就是dp[i-1]*nums[i-1]
• 如果<0，>0，那就是nums[i-1]

• 0，<0，那就是nums[i-1]

• <0，<0，那就是dp[i-1]*nums[i-1]

同样参考最大子数和，还需要一个额外变量来记录最大的…

int maxProduct(vector<int>& nums) {
	int n = nums.size(),maxP = -11;
	vector<int> dp(n+1);
	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		int temp = nums[i - 1] * dp[i - 1];
		if (temp > 0) dp[i] = temp;
		else dp[i] = nums[i - 1];
		maxP = max(maxP, dp[i]);
	}
	return maxP;
}

但是这么做是错误的，就比如-2,3,-4这个例子，最后以-4结尾的子数组最大乘积是24，而不是-4
它参考的不是上一步的最优解3，而是-2和3的乘积-6，也就是说至少这么照搬定义是不符合“最优子结构”的

瞄了题解的提示

这样定义，关键在于对nums[i-1]正负性的讨论，

• 如果nums[i-1]>0，那么我们期望结果最大的话，就希望前面最大的正数乘积
• 如果nums[i-1]<0，那么就期望前面最小的负数乘积

int maxProduct(vector<int>& nums) {
	int n = nums.size(),maxP = -11;
	vector<int> dp(n+1),minRecord(n+1);
	dp[0] = 1,minRecord[0]=1;
	for (int i = 1; i <= n; i++) {
		if (nums[i - 1] > 0) {
			minRecord[i] = min(nums[i - 1], minRecord[i - 1] * nums[i - 1]);
			dp[i] = max(dp[i - 1] * nums[i - 1], nums[i - 1]);
		}
		else {
			minRecord[i] = min(nums[i - 1], dp[i - 1] * nums[i - 1]);
			dp[i] = max(nums[i - 1] * minRecord[i - 1], nums[i - 1]);
		}
		maxP = max(maxP, dp[i]);
	}

	return maxP;
}

这里其实维护了两个dp数组，最大就是我们要要的，只需要再维护一个最小
然后众所周知，一维dp可以空间优化

int maxProduct(vector<int>& nums) {
	// 前面赋初值11是不合理的
	// 这里的三个nums[0]初值其实都是没必要的，但循环遍历nums是必要的
	int maxP = nums[0];
	int maxRecord = nums[0], preMax = 1, minRecord = nums[0], preMin = 1;
	for (int i = 0; i < nums.size(); i++) {
		if (nums[i] > 0) {
			minRecord = min(nums[i], preMin * nums[i]);
			maxRecord = max(preMax * nums[i], nums[i]);
		}
		else {
			minRecord = min(nums[i], preMax * nums[i]);
			maxRecord = max(nums[i] * preMin, nums[i]);
		}
		preMax = maxRecord;
		preMin = minRecord;
		maxP = max(maxP, maxRecord);
	}
	return maxP;
}

本题的关键在于需要一个额外的dp辅助数组，本题是经典最大字数和的变形