延边州建设局网站,WordPress使用自己主题,中国建设教育协会证书查询网站,官方网站百度一下给定一个由整数数组 A 表示的环形数组 C#xff0c;求 C 的非空子数组的最大可能和。 此外#xff0c;子数组最多只能包含固定缓冲区 A 中的每个元素一次。
思路 本道题需要分类成两种情况#xff0c;题目答案为以下两种情况的较大值。 1.最大子区间在序列的中间 这种情况是…给定一个由整数数组 A 表示的环形数组 C求 C 的非空子数组的最大可能和。 此外子数组最多只能包含固定缓冲区 A 中的每个元素一次。
思路 本道题需要分类成两种情况题目答案为以下两种情况的较大值。 1.最大子区间在序列的中间 这种情况是常规的最长子序列做法。 状态转移方程 dp[i] max(nums[i], dp[i-1] nums[i]) 边界条件 dp[0] nums[0] 2.最大子区间被分割成两部分即头尾各一部分 处理分段区间比较麻烦当遇到最大最小问题的时候可以想办法将其反面转化。可以先求出最小子区间和然后用总区间和减去最小子区间和即可。 状态转移方程 dp[i] min(nums[i], dp[i-1] nums[i]) 边界条件 dp[0] nums[0]
坑点 一般遇到此类的题都需要特判一下边界条件。本题需要注意当总区间全为负数时应输出区间中最大的一个负数而不是0。 产生边界的原因 在第二中情况下求最小子区间时若总区间全为负数求出最小区间和即为总区间和。而本题反面转化是基于最大子区间和最小区间是对立的即不能有重合。如此这种情况的最大子区间长度是0不符合题意至少为1的条件。
代码
class Solution {
public:int maxSubarraySumCircular(vectorint nums) {int dp[30005] {0};int len nums.size();dp[0] nums[0];int maxn nums[0];for(int i 1; i len; i){dp[i] max(nums[i], dp[i-1] nums[i]);if(dp[i] maxn)maxn dp[i];}bool flag true;int dp2[30005] {0};dp2[0] nums[0];int minn nums[0];int sum nums[0];if(nums[0] 0)flag false;for(int i 1; i len; i){if(nums[i] 0)flag false;sum nums[i];dp2[i] min(nums[i], dp2[i-1] nums[i]);if(dp2[i] minn)minn dp2[i];}if(flag true)return maxn;if(sum - minn maxn)maxn sum - minn;return maxn;}
};
