写在前面

青训营接近尾声，蒜法蒻媾下个月打算法氵赛，每天一道难题冲冲冲！今天准备复习的是最大连续子数组和问题，众所周知最大连续子数组和的经典解法是Kadane算法，下面来看看题目

问题描述

小C拿到了一个数组，他可以进行最多一次操作：将一个元素修改为任意给定的x。小C想知道，经过这次修改后，能够得到的连续子数组的最大和是多少。

测试样例

样例1：

输入：n = 5 ,x = 10 ,a = [5, -1, -5, -3, 2]
输出：15

样例2：

输入：n = 2 ,x = -3 ,a = [-5, -2]
输出：-2

样例3：

输入：n = 6 ,x = 10 ,a = [4, -2, -11, -1, 4, -1]
输出：15

解题思路

首先了解一下Kadane算法的基本思路，Kadane算法是一个经典的用于解决最大连续子数组和的动态规划算法，通过维护更新一个局部最大值和一个全局最大值来得到最优解。这个算法实现也很好理解，一般分为以下两步：

1. 初始化： 初始化局部最大变量max_ending_here和全局最大变量max_so_far为数组第一个元素.

2. 遍历数组： 遍历数组，若局部最大值加上当前值比局部最大值还要大，则扩展子数组更新最大值，反之从当前元素开始一个新的子数组求和，更新完局部最大值后再把局部最大值和全局最大值比较，更新全局最大值.

实现完Kadane算法后，这题剩下的步骤就很简单了，再遍历数组一次，依次修改每个元素，计算每次修改后的最大连续子数组和，再恢复修改的元素遍历下一个，直到遍历完成返回最大值。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

int kadane(const std::vector<int>& a) {
    // Kadane算法实现
    int max_ending_here = a[0];
    int max_so_far = a[0];
    for (int i = 1; i < a.size(); ++i) {
        max_ending_here = std::max(a[i], max_ending_here + a[i]);
        max_so_far = std::max(max_so_far, max_ending_here);
    }
    return max_so_far;
}

int solution(int n, int x, std::vector<int> a) {
    // 尝试修改每个元素为x，计算修改后的最大子数组和
    int max_sum_with_change = std::numeric_limits<int>::min(); //给个很小的数
    for (int i = 0; i < n; ++i) {
        int original_value = a[i];
        a[i] = x;  // 修改当前元素为x
        int current_max_sum = kadane(a);
        max_sum_with_change = std::max(max_sum_with_change, current_max_sum);
        a[i] = original_value;  // 恢复原值
    }
  
    // 返回不修改和修改后的最大子数组和中的最大值
    return max_sum_with_change;
}

int main() {
    std::cout << (solution(5, 10, {5, -1, -5, -3, 2}) == 15) << std::endl;
    std::cout << (solution(2, -3, {-5, -2}) == -2) << std::endl;
    std::cout << (solution(6, 10, {4, -2, -11, -1, 4, -1}) == 15) << std::endl;
    std::cout << (solution(16, 1, {17,17,4,13,11,3,6,13,7,13,13,13,6,16,6,11}) == 167) << std::endl;
}