企业官网建设流程全解析

广州天河区网站建设,网站定制开发需要什么资质,网站增加流量,网站建设手机源码一、问题理解问题描述给定一个整数数组 nums#xff0c;找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。示例text输入#xff1a;nums [-2,1,-3,4,-1,2,1,-5,4] 输出#xff1a;6 解释#xff1a;连续子数组 [4…一、问题理解问题描述给定一个整数数组nums找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。示例text输入nums [-2,1,-3,4,-1,2,1,-5,4] 输出6 解释连续子数组 [4,-1,2,1] 的和最大为 6 输入nums [1] 输出1 输入nums [5,4,-1,7,8] 输出23二、核心思路前缀和 最小前缀和追踪暴力解法的局限性枚举所有子数组并计算和时间复杂度为 O(n²)效率极低。前缀和优化思路前缀和定义prefix[i]表示从数组开头到第i个元素不包括第i个的和核心观察子数组nums[i:j]的和 prefix[j] - prefix[i]对于每个位置j要找到prefix[j] - prefix[i]的最大值就是要找到prefix[i]的最小值其中i j优化策略遍历数组计算前缀和同时维护到当前位置的最小前缀和用当前前缀和减去最小前缀和得到以当前位置为结尾的最大子数组和更新全局最大和三、代码逐行解析pythonfrom typing import List import math class Solution: def maxSubArray(self, nums: List[int]) - int: # 1. 初始化 # ans: 存储最大子数组和初始化为负无穷确保第一个元素可以更新它 ans -math.inf # min_pre_sum: 记录到当前位置的最小前缀和初始为0空数组的前缀和 min_pre_sum 0 # pre_sum: 当前前缀和初始为0 pre_sum 0 # 2. 遍历数组 for x in nums: # 2.1 更新当前前缀和 pre_sum x # 2.2 计算以当前位置为结尾的最大子数组和 # 当前前缀和 - 之前的最小前缀和 以当前位置为结尾的最大子数组和 ans max(ans, pre_sum - min_pre_sum) # 2.3 更新最小前缀和 # 注意先计算ans再更新min_pre_sum确保min_pre_sum是当前位置之前的最小值 min_pre_sum min(min_pre_sum, pre_sum) # 3. 返回结果 return ans四、关键步骤详解1. 为什么需要min_pre_sum对于任意位置j以j结尾的最大子数组和为textmax_sum_ending_at_j max(prefix[j] - prefix[i]) for all i j由于prefix[j]是固定的要使差值最大就要使prefix[i]最小。因此我们只需要维护到当前位置的最小前缀和即可。2. 为什么min_pre_sum初始化为 0空数组的前缀和为 0当数组只有一个元素时最大子数组和就是该元素本身对于第一个元素xpre_sum xans max(-∞, x - 0) x这样处理确保了单个元素的情况也能正确计算3. 为什么先计算ans再更新min_pre_sum我们需要的是当前位置之前的最小前缀和不包括当前位置。如果先更新min_pre_sum可能会用到当前前缀和这会导致计算出的子数组可能为空先计算ans确保min_pre_sum是严格在当前位置之前的最小值五、算法步骤演示以nums [-2, 1, -3, 4, -1, 2, 1, -5, 4]为例步骤xpre_summin_pre_sumpre_sum - min_pre_sumans初始-00--∞1-2-20-2max(-∞, -2) -2更新--2min(0, -2) -2--221-1-21max(-2, 1) 1更新--1min(-2, -1) -2-13-3-4-2-2max(1, -2) 1更新--4min(-2, -4) -4-1440-44max(1, 4) 4更新-0min(-4, 0) -4-45-1-1-43max(4, 3) 4更新--1min(-4, -1) -4-4621-45max(4, 5) 5更新-1min(-4, 1) -4-5712-46max(5, 6) 6更新-2min(-4, 2) -4-68-5-3-41max(6, 1) 6更新--3min(-4, -3) -4-6941-45max(6, 5) 6最终结果6六、与其他解法的对比1. 动态规划Kadane算法pythondef maxSubArray_kadane(nums): max_sum nums[0] current_sum nums[0] for i in range(1, len(nums)): current_sum max(nums[i], current_sum nums[i]) max_sum max(max_sum, current_sum) return max_sum复杂度时间复杂度O(n)空间复杂度O(1)与本题解法的关系Kadane算法是动态规划的思想dp[i]表示以i结尾的最大子数组和本题解法是前缀和的思想最大子数组和 当前前缀和 - 最小前缀和两种方法本质相同都达到了 O(n) 时间复杂度和 O(1) 空间复杂度2. 分治法pythondef maxSubArray_divide_conquer(nums): def helper(left, right): if left right: return nums[left] mid (left right) // 2 # 左半部分最大子数组和 left_max helper(left, mid) # 右半部分最大子数组和 right_max helper(mid 1, right) # 跨中点的最大子数组和 left_sum nums[mid] left_temp nums[mid] for i in range(mid - 1, left - 1, -1): left_temp nums[i] left_sum max(left_sum, left_temp) right_sum nums[mid 1] right_temp nums[mid 1] for i in range(mid 2, right 1): right_temp nums[i] right_sum max(right_sum, right_temp) cross_max left_sum right_sum return max(left_max, right_max, cross_max) return helper(0, len(nums) - 1)复杂度时间复杂度O(n log n)空间复杂度O(log n)递归栈空间七、复杂度分析时间复杂度O(n)只遍历数组一次每次循环执行常数时间操作加法、减法、比较空间复杂度O(1)只使用了常数个额外变量ans、min_pre_sum、pre_sum八、优化技巧与变体1. 处理全负数数组pythondef maxSubArray_all_negative(nums): # 如果确定数组全为负数可以先找到最大值 max_val max(nums) if max_val 0: return max_val # 否则使用原算法 ans -math.inf min_pre_sum 0 pre_sum 0 for x in nums: pre_sum x ans max(ans, pre_sum - min_pre_sum) min_pre_sum min(min_pre_sum, pre_sum) return ans2. 返回最大子数组本身pythondef maxSubArray_with_subarray(nums): ans -math.inf min_pre_sum 0 pre_sum 0 start 0 end 0 temp_start 0 for i, x in enumerate(nums): pre_sum x if pre_sum - min_pre_sum ans: ans pre_sum - min_pre_sum start temp_start end i if pre_sum min_pre_sum: min_pre_sum pre_sum temp_start i 1 return ans, nums[start:end1] # 示例 nums [-2, 1, -3, 4, -1, 2, 1, -5, 4] max_sum, subarray maxSubArray_with_subarray(nums) print(f最大和: {max_sum}, 子数组: {subarray}) # 输出: 最大和: 6, 子数组: [4, -1, 2, 1]3. 处理环形数组LeetCode 918pythondef maxSubarraySumCircular(nums): # 环形数组的最大子数组和有两种情况 # 1. 最大子数组在数组中间非环形 # 2. 最大子数组跨越数组首尾环形 # 情况2 数组总和 - 最小子数组和 total sum(nums) max_sum nums[0] min_sum nums[0] cur_max nums[0] cur_min nums[0] for i in range(1, len(nums)): cur_max max(nums[i], cur_max nums[i]) max_sum max(max_sum, cur_max) cur_min min(nums[i], cur_min nums[i]) min_sum min(min_sum, cur_min) # 特殊情况如果所有数都是负数则max_sum就是最大负数 if max_sum 0: return max_sum # 环形情况的最大值 max(非环形最大和, 总和 - 最小和) return max(max_sum, total - min_sum)九、常见问题与解答Q1: 如果数组全为负数算法还正确吗A1: 正确。算法会返回最大的负数。例如nums [-2, -1]第一步pre_sum -2,ans -2,min_pre_sum -2第二步pre_sum -3,ans max(-2, -3 - (-2)) -1,min_pre_sum -3返回-1这是正确的最大子数组是[-1]和为-1Q2: 为什么min_pre_sum初始化为 0 而不是nums[0]A2: 初始化为 0 可以正确处理只有一个元素的情况。如果初始化为nums[0]对于nums [1]pre_sum 1,ans 1 - 1 0这是错误的初始化为 0pre_sum 1,ans 1 - 0 1这是正确的Q3: 这个算法和 Kadane 算法哪个更好A3: 两者时间复杂度都是 O(n)空间复杂度都是 O(1)。Kadane 算法更直观直接表达了动态规划的思想前缀和算法更数学化展示了问题本质在实际应用中Kadane 算法更常用但两种方法都是正确的十、相关题目1. LeetCode 152. 乘积最大子数组pythondef maxProduct(nums): if not nums: return 0 max_prod nums[0] min_prod nums[0] result nums[0] for i in range(1, len(nums)): # 由于负负得正需要同时维护最大和最小乘积 temp_max max(nums[i], max_prod * nums[i], min_prod * nums[i]) temp_min min(nums[i], max_prod * nums[i], min_prod * nums[i]) max_prod, min_prod temp_max, temp_min result max(result, max_prod) return result2. LeetCode 918. 环形子数组的最大和前面已提到3. LeetCode 121. 买卖股票的最佳时机pythondef maxProfit(prices): if not prices: return 0 min_price prices[0] max_profit 0 for price in prices[1:]: # 更新最大利润 max_profit max(max_profit, price - min_price) # 更新最低价格 min_price min(min_price, price) return max_profit十一、总结核心要点前缀和是关键将子数组和问题转化为前缀和之差问题最小前缀和追踪对于每个位置最大子数组和 当前前缀和 - 之前的最小前缀和时间复杂度优化从暴力解法的 O(n²) 优化到 O(n)算法步骤初始化ans为负无穷min_pre_sum为 0pre_sum为 0遍历数组中的每个元素更新当前前缀和pre_sum更新答案ans max(ans, pre_sum - min_pre_sum)更新最小前缀和min_pre_sum min(min_pre_sum, pre_sum)返回ans适用场景需要找到连续子数组的最大和数组可能包含负数要求时间复杂度为 O(n)扩展思考这个解法展示了如何将看似复杂的问题最大子数组和转化为简单的数学关系前缀和之差通过追踪最小值来优化计算。这种思想可以应用到许多其他问题中如最小子数组和子数组和接近某个目标值二维数组的最大子矩阵和掌握前缀和最小前缀和追踪的解法不仅能够解决最大子数组和问题还能够解决一系列类似的子数组和问题是面试中非常重要的算法技巧。