题解 | #学生查询#
连续子数组的最大乘积
http://www.nowcoder.com/practice/fd8c819c07c9493887bfac8549c119f4
本题难点在于负数的处理
我的处理过程：使用temp记录当前访问元素之前最近出现的负数的下标，
当前元素为负数时，首先先将数据累乘过去；然后当temp >= 1时，转态转移方程为：dp[i] = max(dp[i], dp[i] * dp[temp - 1]);
我的处理过程：使用temp记录当前访问元素之前最近出现的负数的下标，
当前元素为负数时，首先先将数据累乘过去；然后当temp >= 1时，转态转移方程为：dp[i] = max(dp[i], dp[i] * dp[temp - 1]);
当前元素为正数时，转态转移方程为：dp[i] = max(dp[i], dp[i] * dp[i - 1]);
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 2e5 + 10;
int arr[MAXN];
int dp[MAXN];
int main() {
int n;
while(cin >> n) {
for(int i = 0; i < n; ++i) {
cin >> arr[i];
dp[i] = arr[i];
}
int maximum = arr[0];
int temp = -1; //记录最近负数下标
if(arr[0] < 0) {
temp = 0;
}
for(int i = 1; i < n; ++i) {
if(arr[i] < 0) {
if(temp != -1) { //前面有负数就累乘过去,没负数就不管
for(int j = i - 1; j >= temp; --j) {
dp[i] *= arr[j];
}
if(temp >= 1) {
dp[i] = max(dp[i], dp[i] * dp[temp -1]);
}
}
temp = i;
} else {
dp[i] = max(dp[i], dp[i] * dp[i - 1]);
}
maximum = max(maximum, dp[i]);
}
cout << maximum << endl;
}
return 0;
}
传音控股公司福利 304人发布