欢迎光临
我们一直在努力

题解:学而思编程 删数最大子段和

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来,并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构,旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏:算法题解:C++与Python实现!

附上汇总贴:算法竞赛备考冲刺必刷题(C++) | 汇总


【题目来源】

学而思编程:删数最大子段和

【题目描述】

给出一个数组

a

1

,

a

2

,

⋯

 

,

a

n

a_1,a_2,⋯ ,a_n

a1​,a2​,⋯ ,an​,删除一个元素后,求它的最大子段和。(子段是指数组中连续的一段元素)

删除的元素可以由你自由选择,但是不能不删除任何元素,输出你能得到的最大的子段和。

【输入】

第

1

1

1 行,

1

1

1 个正整数

n

n

n。

第

2

2

2 行,

n

n

n 个整数

a

1

,

a

2

,

⋯

 

,

a

n

a_1,a_2,⋯ ,a_n

a1​,a2​,⋯ ,an​。

【输出】

输出能得到的最大的子段和。

【输入样例】

5
9 5 -6 -10 7

【输出样例】

15

【核心思想】

  • 问题分析:给定长度为

    n

    n

    n 的序列

    a

    1

    ,

    a

    2

    ,

    …

    ,

    a

    n

    a_1, a_2, \\ldots, a_n

    a1​,a2​,…,an​,需要删除一个元素后,求剩余数组的最大子段和。等价于求两段不相邻的最大子段和(删除位置

    i

    i

    i 后,左边

    a

    [

    1..

    i

    −

    1

    ]

    a[1..i-1]

    a[1..i−1] 和右边

    a

    [

    i

    +

    1..

    n

    ]

    a[i+1..n]

    a[i+1..n] 各取一段)。这是一个线性动态规划的扩展问题。

  • 算法选择:

    • 前缀DP:

      d

      p

      1

      [

      i

      ]

      dp1[i]

      dp1[i] 表示以

      a

      [

      i

      ]

      a[i]

      a[i] 结尾的最大子段和(正向)

    • 后缀DP:

      d

      p

      2

      [

      i

      ]

      dp2[i]

      dp2[i] 表示以

      a

      [

      i

      ]

      a[i]

      a[i] 开头的最大子段和(反向)

    • 组合枚举:枚举删除位置

      i

      i

      i,计算

      d

      p

      1

      [

      i

      −

      1

      ]

      +

      d

      p

      2

      [

      i

      +

      1

      ]

      dp1[i-1] + dp2[i+1]

      dp1[i−1]+dp2[i+1] 的最大值

  • 关键步骤:

    • 特判全负数:若所有

      a

      [

      i

      ]

      <

      0

      a[i] < 0

      a[i]<0,答案为

      max

      ⁡

      (

      a

      [

      i

      ]

      )

      \\max(a[i])

      max(a[i])(只能选最大的负数)

    • 计算前缀最大子段和:
      • d

        p

        1

        [

        i

        ]

        =

        max

        ⁡

        (

        d

        p

        1

        [

        i

        −

        1

        ]

        +

        a

        [

        i

        ]

        ,

        a

        [

        i

        ]

        )

        dp1[i] = \\max(dp1[i-1] + a[i], a[i])

        dp1[i]=max(dp1[i−1]+a[i],a[i])

      • 表示以

        a

        [

        i

        ]

        a[i]

        a[i] 结尾的最大子段和

    • 计算后缀最大子段和:
      • d

        p

        2

        [

        i

        ]

        =

        max

        ⁡

        (

        d

        p

        2

        [

        i

        +

        1

        ]

        +

        a

        [

        i

        ]

        ,

        a

        [

        i

        ]

        )

        dp2[i] = \\max(dp2[i+1] + a[i], a[i])

        dp2[i]=max(dp2[i+1]+a[i],a[i])

      • 表示以

        a

        [

        i

        ]

        a[i]

        a[i] 开头的最大子段和

    • 枚举删除位置

      i

      i

      i(

      1

      ≤

      i

      ≤

      n

      1 \\leq i \\leq n

      1≤i≤n):

      • 左边最大贡献:

        d

        p

        1

        [

        i

        −

        1

        ]

        dp1[i-1]

        dp1[i−1](以

        i

        −

        1

        i-1

        i−1 结尾的最大子段)

      • 右边最大贡献:

        d

        p

        2

        [

        i

        +

        1

        ]

        dp2[i+1]

        dp2[i+1](以

        i

        +

        1

        i+1

        i+1 开头的最大子段)

      • 更新答案:

        a

        n

        s

        =

        max

        ⁡

        (

        a

        n

        s

        ,

        d

        p

        1

        [

        i

        −

        1

        ]

        +

        d

        p

        2

        [

        i

        +

        1

        ]

        )

        ans = \\max(ans, dp1[i-1] + dp2[i+1])

        ans=max(ans,dp1[i−1]+dp2[i+1])

  • 时间/空间复杂度:

    • 时间复杂度:

      O

      (

      n

      )

      O(n)

      O(n),三次线性遍历(前缀DP、后缀DP、枚举删除位置)

    • 空间复杂度:

      O

      (

      n

      )

      O(n)

      O(n),存储

      d

      p

      1

      dp1

      dp1 和

      d

      p

      2

      dp2

      dp2 数组

  • 前后缀DP组合的核心思想:

    • 问题转化:删除一个元素后的最大子段和 = 左边某段 + 右边某段(两段不相邻)
    • 前缀预处理:快速获取以任意位置结尾的最大子段和
    • 后缀预处理:快速获取以任意位置开头的最大子段和
    • 枚举分割点:通过枚举删除位置,组合左右两段的最优解
    • 适用于区间分割、删除/插入元素后的最优解问题
  • 【算法标签】

    #线性DP-一维

    【代码详解】

    #include <bits/stdc++.h>
    using namespace std;

    const int N = 1005;
    int n, a[N]; // n: 数组大小,a: 数组元素
    int dp1[N], dp2[N]; // dp1: 从前向后的最大子段和,dp2: 从后向前的最大子段和

    int main()
    {
    cin >> n; // 读入数组大小
    bool flag = 0; // 标记是否存在非负数
    int mx = –1e9; // 记录数组中的最大值
    for (int i = 1; i <= n; i++)
    {
    cin >> a[i]; // 读入数组元素
    if (a[i] >= 0) // 如果存在非负数
    {
    flag = 1;
    }
    mx = max(mx, a[i]); // 更新最大值
    }

    // 如果所有数都是负数,则最大子段和就是最大的那个负数
    if (flag == 0)
    {
    cout << mx << endl;
    return 0;
    }

    // 计算从前向后的最大子段和
    // dp1[i]表示以a[i]结尾的最大子段和
    dp1[1] = a[1];
    for (int i = 2; i <= n; i++)
    {
    dp1[i] = max(dp1[i – 1] + a[i], a[i]);
    }

    // 计算从后向前的最大子段和
    // dp2[i]表示以a[i]开头的最大子段和
    dp2[1] = a[n];
    for (int i = n; i >= 1; i—) // 这里有个小问题,应该是从n-1开始
    {
    dp2[i] = max(dp2[i + 1] + a[i], a[i]);
    }

    int maxn = –1e9; // 记录最大两段子段和
    for (int i = 1; i <= n; i++)
    {
    // 计算不相邻的两段最大子段和
    // 注意:这里dp1[i-1]和dp2[i+1]分别表示第i个元素左边和右边的最大子段和
    maxn = max(maxn, dp1[i – 1] + dp2[i + 1]);
    }

    cout << maxn << endl; // 输出结果
    return 0;
    }

    【运行结果】

    5
    9 5 -6 -10 7
    15

    赞(0)
    未经允许不得转载:171主机测评 » 题解:学而思编程 删数最大子段和
    分享到: 更多 (0)

    评论 抢沙发

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址