怎么设置网站支付功能,mstsc做网站,凡科做的网站可以在百度搜到吗,河南国基建设集团--官方网站918. 环形子数组的最大和
给定一个长度为 n 的环形整数数组 nums #xff0c;返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上#xff0c; nums[i] 的下一个元素是 nums[(i 1) % n] #xff0c; nums[i] 的前一个元素是…918. 环形子数组的最大和
给定一个长度为 n 的环形整数数组 nums 返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上 nums[i] 的下一个元素是 nums[(i 1) % n] nums[i] 的前一个元素是 nums[(i - 1 n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上对于子数组 nums[i], nums[i 1], ..., nums[j] 不存在 i k1, k2 j 其中 k1 % n k2 % n 。 示例 1
输入nums [1,-2,3,-2]
输出3
解释从子数组 [3] 得到最大和 3示例 2
输入nums [5,-3,5]
输出10
解释从子数组 [5,5] 得到最大和 5 5 10示例 3
输入nums [3,-2,2,-3]
输出3
解释从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3提示
n nums.length1 n 3 * 104-3 * 104 nums[i] 3 * 104 class Solution {
public:int maxSubarraySumCircular(vectorint nums) {int nnums.size();vectorvectorint dp(n,vectorint(2,nums[0]));dp[0][0]nums[0];dp[0][1]nums[0];int sumnums[0],maxnnums[0],minnnums[0];for(int i1;in;i){//每个元素都当做是子数组的最后一个元素分别求出两个状态最大子数组和和最小子数组和dp[i][0]max(dp[i-1][0]nums[i],nums[i]);maxnmax(dp[i][0],maxn);dp[i][1]min(dp[i-1][1]nums[i],nums[i]);minnmin(dp[i][1],minn);sumnums[i];}return maxn0?max(maxn,sum-minn):maxn;}
};
