国外网站建设现状网站建设优化文档

国外网站建设现状,网站建设优化文档,网站开发有哪几个阶段,教师遭网课入侵直播录屏曝光口题目理解 给定价格数组 prices 和策略数组 strategy#xff0c;策略可以是#xff1a; -1: 买入0: 持有1: 卖出 利润 Σ(strategy[i] prices[i]) 我们可以进行最多一次修改#xff1a;选择连续 k 个元素#xff0c;前 k/2 个改为 0#xff0c;后 k/2 个改为 1。 求最大可…题目理解给定价格数组prices和策略数组strategy策略可以是-1: 买入0: 持有1: 卖出利润 Σ(strategy[i] × prices[i])我们可以进行最多一次修改选择连续 k 个元素前 k/2 个改为 0后 k/2 个改为 1。求最大可能利润。解题思路方法一暴力枚举朴素思路最直接的想法是枚举所有可能的修改位置不修改的情况从索引 0, 1, 2, …, n-k 开始修改每次计算修改后的总利润取最大值。时间复杂度: O(n²) - 枚举 O(n) 个位置每次重新计算总利润 O(n)方法二前缀和优化推荐观察到暴力方法有大量重复计算。我们可以用前缀和优化。核心思想设原始利润为base Σ(strategy[i] × prices[i])当我们修改从位置 i 开始的 k 个元素时修改前: [i, i1, ..., ik/2-1, ik/2, ..., ik-1] 修改后: [ 全部变成0 ][ 全部变成1 ]设p1 i,p2 i k/2 - 1前半部分变成 0p3 i k/2,p4 i k - 1后半部分变成 1则原利润在 [p1, p2] 区间:base1 Σ(strategy[j] × prices[j])修改后变为 0原利润在 [p3, p4] 区间:base2 Σ(strategy[j] × prices[j])修改后变为Σprices[j]关键公式新利润 base - base1 - base2 Σprices[p3~p4]即profit_diff Σprices[p3~p4] - base1 - base2只有当profit_diff 0时修改才能提升利润。前缀和预处理使用两个前缀和数组prefixSums[i]: prices 的前缀和用于快速计算价格区间和baseSums[i]: strategy[j] × prices[j] 的前缀和用于快速计算原利润这样每次查询区间和的时间从 O(k) 降到 O(1)。时间复杂度: O(n) - 预处理 O(n)枚举 O(n) 个位置每次 O(1) 计算空间复杂度: O(n)代码实现funcmaxProfit(prices[]int,strategy[]int,kint)int64{n:len(prices)// 前缀和预处理prefixSums:make([]int64,n1)// prices 的前缀和baseSums:make([]int64,n1)// strategy[i]*prices[i] 的前缀和varbaseint64fori:0;in;i{prefixSums[i1]prefixSums[i]int64(prices[i])baseint64(strategy[i])*int64(prices[i])baseSums[i1]baseSums[i]int64(strategy[i])*int64(prices[i])}// 边界k n 时无法修改ifkn{returnbase}maxProfit:base// 枚举所有修改起点fori:0;in-k;i{p1:i p2:ik/2-1p3:ik/2p4:ik-1// 原利润中被修改部分的贡献base1:baseSums[p21]-baseSums[p1]base2:baseSums[p41]-baseSums[p3]// 修改后后半部分的贡献全为1priceSum:prefixSums[p41]-prefixSums[p3]// 新利润 原利润 - 被移除部分 新增部分profit:base-base1-base2priceSumifprofitmaxProfit{maxProfitprofit}}returnmaxProfit}示例演示以prices [4,2,8], strategy [-1,0,1], k 2为例预处理base (-1)×4 0×2 1×8 4prefixSums [0, 4, 6, 14]baseSums [0, -4, -4, 4]枚举修改位置i0: 修改 [0,1] → [0,1,1]base1 baseSums[1] - baseSums[0] -4base2 0 (p3p41)priceSum prefixSums[2] - prefixSums[1] 2profit 4 - (-4) - 0 2 10✓i1: 修改 [1,2] → [-1,0,1] (无变化)profit 4最大利润: 10复杂度分析时间复杂度: O(n)其中 n 是数组长度空间复杂度: O(n)用于存储前缀和数组总结本题的关键是识别暴力枚举中的重复计算通过前缀和实现 O(1) 的区间和查询将时间复杂度从 O(n²) 优化到 O(n)。这是一个典型的「暴力→优化」的思维过程。