百度装修网站,软膜做网站有用吗,ui网页设计师,中国制造网外贸平台中文版诸神缄默不语-个人CSDN博文目录 力扣刷题笔记 文章目录 1. 暴力搜索2. 动态规划3. 前缀和 1. 暴力搜索
直接用2个指针从索引0开始找到最后一个索引#xff0c;时间复杂度大概是 O ( n 2 ) O(n^2) O(n2)吧#xff0c;总之这么搞不行#xff0c;以下是我用Python写的一些典型…诸神缄默不语-个人CSDN博文目录 力扣刷题笔记 文章目录 1. 暴力搜索2. 动态规划3. 前缀和 1. 暴力搜索
直接用2个指针从索引0开始找到最后一个索引时间复杂度大概是 O ( n 2 ) O(n^2) O(n2)吧总之这么搞不行以下是我用Python写的一些典型失败案例
class Solution:def maxAbsoluteSum(self, nums: List[int]) - int:max_abs0nums_lenlen(nums)for pointer1 in range(nums_len):for pointer2 in range(pointer1,nums_len):sub_numsnums[pointer1:pointer21]max_absmax(max_abs,abs(sum(sub_nums)))return max_abs↑会超时这个我觉得应该是sum()的问题所以做了改进
class Solution:def maxAbsoluteSum(self, nums: List[int]) - int:sum_table[[0 for _ in range(len(nums))] for _ in range(len(nums))]for i in range(len(nums)):sum_table[i][i]nums[i]for i in range(len(nums)):for j in range(i1,len(nums)):sum_table[i][j]sum_table[i][j-1]nums[j]max_abs0for i in sum_table:for j in i:max_absmax(max_abs,abs(j))return max_abs↑这个又会爆内存我骂骂咧咧。 这个我一开始猜是因为0太多了所以把所有一直都是0的部分给删除了
class Solution:def maxAbsoluteSum(self, nums: List[int]) - int:sum_table[[0 for _ in range(len(nums)-i)] for i in range(len(nums))]for i in range(len(nums)):sum_table[i][0]nums[i]for i in range(len(nums)):for j in range(1,len(nums)-i):sum_table[i][j]sum_table[i][j-1]nums[ji]max_abs0for i in sum_table:for j in i:max_absmax(max_abs,abs(j))return max_abs↑还是会爆内存 继续缩
class Solution:def maxAbsoluteSum(self, nums: List[int]) - int:max_abs0for i in range(len(nums)):pre_sumnums[i]max_absmax(max_abs,abs(pre_sum))for j in range(i1,len(nums)):pre_sumpre_sumnums[j]max_absmax(max_abs,abs(pre_sum))return max_abs这回超时了
2. 动态规划
然后我就去看题解了。
来自官方题解https://leetcode.cn/problems/maximum-absolute-sum-of-any-subarray/solutions/2372374/ren-yi-zi-shu-zu-he-de-jue-dui-zhi-de-zu-qerr/
在一组数字中绝对值的最大值可能是最大的值的绝对值也可能是最小值的绝对值。 所以找子数组和绝对值的最大值就要找最大的子数组和和最小的子数组和。 所以解决方案是分别计算这两种情况在找最大的子数组和时遍历数组保留到上一个数字为止的全局子数组最大和global_max有上一个数字在的子数组的最大和sumable_max或者00的意思就是甩掉上一个数字如果新数字sumable_max比positiveMax还高就更新global_max如果这个数字加进sumable_max大于0了那对后续数字而言加sumable_max是可以更大的我在说什么反正就是这个意思否则不如直接重开。 找最小的子数组和时就完全反过来保留全局最小和global_min可加最小和sumable_min或0如果新数字sumable_minglobal_min就更新global_min如果新数字sumable_min0那就白给立刻重开。
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
class Solution:def maxAbsoluteSum(self, nums: List[int]) - int:global_max0sumable_max0global_min0sumable_min0for i in nums:sumable_maxiglobal_maxmax(global_max,sumable_max)sumable_maxmax(0,sumable_max)sumable_miniglobal_minmin(global_min,sumable_min)sumable_minmin(0,sumable_min)return max(abs(global_max),abs(global_min))官方Java代码
class Solution {public int maxAbsoluteSum(int[] nums) {int positiveMax 0, negativeMin 0;int positiveSum 0, negativeSum 0;for (int num : nums) {positiveSum num;positiveMax Math.max(positiveMax, positiveSum);positiveSum Math.max(0, positiveSum);negativeSum num;negativeMin Math.min(negativeMin, negativeSum);negativeSum Math.min(0, negativeSum);}return Math.max(positiveMax, -negativeMin);}
}3. 前缀和
前缀和指的是在数组最前面加个0没这个的话一个子数组没法是最大的前缀和本身了从第1个数字到当前数字的和任何子数组和显然都是某2个前缀和的差值最大的子数组和绝对值显然就是最大前缀和-最小前缀和
Python 3有内置函数
class Solution:def maxAbsoluteSum(self, nums: List[int]) - int:s list(accumulate(nums, initial0)) # nums 的前缀和return max(s) - min(s)Java实现的示例
class Solution {public int maxAbsoluteSum(int[] nums) {int nnums.length;int pre0;int max0;int min0;for(int i0;in;i){prenums[i];maxMath.max(max,pre);minMath.min(min,pre);}return max-min;}
}
