1.最大子段和 考虑dp dp[i] = max(dp[i - 1] + a[i], a[i])
即,要不从上一段拼接过来,要么另起新的一段
int res = -1e18;
for(int i = 1; i <= n; i ++ )
{
cin >> a[i];
dp[i] = max(dp[i - 1] + a[i], a[i]);
res = max(res, dp[i]);
}
2.最小子段和 思路:对数组全部取负,然后跑最大子段和,然后对res取负
int res = -1e18; //注意这里求最小赋值的是负的最小
for(int i = 1; i <= n; i ++ )
{
cin >> a[i];
dp[i] = max(dp[i - 1] - a[i], -a[i]);
res = max(res, dp[i]);
}
res = - res;
感谢
感谢
感谢