山东省建设局网站,重庆律师网站建设,零陵网站建设,网站如何做快照题目#xff1a;给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。子数组 是数组中的一个连续部分。方法一#xff1a;贪心算法原理#xff1a;若当前指针所指元素之前的和小…题目给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。子数组 是数组中的一个连续部分。方法一贪心算法原理若当前指针所指元素之前的和小于0则丢弃当前元素之前的数列。三个变量 前面数之和 当前数之和 最大和int maxSubArray(int* nums, int numsSize){int preSum 0,MaxSum -10000,curSum nums[0]; //初始化之前和为0当前和为第一个元素最大和为一个很大的负数。for(int i 0;i numsSize;i ){ //遍历数组if(i0) preSum 0;else preSum nums[i-1];if(preSum0){ //如果之前和小于0则把当前元素赋值给当前和之前和重新变为0curSum nums[i]; preSum 0;}else{curSum preSum nums[i]; //如果之前和不小于0则把当前元素之前和赋值给当前和}if(curSumMaxSum){ //如果当前和大于最大和则赋值给最大和MaxSum curSum;}}return MaxSum;
}
复杂度时间O(n)空间O(1)。方法二动态规划若前一个元素大于0则将其加到当前元素上。int maxSubArray(int* nums, int numsSize) {int pre 0, maxAns nums[0]; //初始化前一个元素为0最大子数组为0for (int i 0; i numsSize; i) { //遍历数组pre fmax(pre nums[i], nums[i]);//返回两个数中最大的数赋值给前一个元素maxAns fmax(maxAns, pre);//每一个当前元素和当前最大子数组和比较}return maxAns;
}
动态规划适用场景能够利用动态规划算法求解的问题都会具备以下两点性质最优子结构 利用动态规划算法求解问题的第一步就是需要刻画问题最优解的结构并且如果一个问题的最优解包含其子问题的最优解则此问题具备最优子结构的性质。因此判断某个问题是否适合用动态规划算法需要判断该问题是否具有最优子结构。Tips: 最优子结构的定义主要是在于当前问题的最优解可以从子问题的最优解得出当子问题满足最优解之后才可以通过子问题的最优解获得原问题的最优解。重叠子问题 适合用动态规划算法去求解的最优化问题应该具备的第二个性质是问题的子问题空间必须足够” 小 “也就是说原问题递归求解时会重复相同的子问题而不是一直生成新的子问题。如果原问题的递归算法反复求解相同的子问题我们就称该最优化问题具有重叠子问题。Tips: 在这里我们需要注意是与适用动态规划算法去求解的问题具备重叠子问题性质相反前面我们介绍的分治算法递归解决问题时问题的子问题都是互不影响相互独立的这个也是我们在选用动态规划算法还是分治法解决问题时的一个判断条件。时间复杂度O(n)其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。空间复杂度O(1)。我们只需要常数空间存放若干变量。注和贪心算法一样动态规划算法只是一种思想不是像排序算法一样有具体的代码。方法三分治算法分治算法Divide and Conquer将序列从中分为左右两个子序列。递归求得两个子列的最大和。从中分点分头向左、右两边扫描找出跨过分界线的最大子列和。输出这三个子列和最大的一个。struct Status {int lSum, rSum, mSum, iSum;
};struct Status pushUp(struct Status l, struct Status r) {int iSum l.iSum r.iSum;int lSum fmax(l.lSum, l.iSum r.lSum);int rSum fmax(r.rSum, r.iSum l.rSum);int mSum fmax(fmax(l.mSum, r.mSum), l.rSum r.lSum);return (struct Status){lSum, rSum, mSum, iSum};
};struct Status get(int* a, int l, int r) {if (l r) {return (struct Status){a[l], a[l], a[l], a[l]};}int m (l r) 1;struct Status lSub get(a, l, m);struct Status rSub get(a, m 1, r);return pushUp(lSub, rSub);
}int maxSubArray(int* nums, int numsSize) {return get(nums, 0, numsSize - 1).mSum;
}
