0612#连续子数组最大和

本文主要是介绍0612#连续子数组最大和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

小红拿到了一个数组，她希望进行最多一次操作：将一个元素修改为x。小红想知道，最终的连续子数组最大和最大是多少？

输入描述

第一行输入一个正整数t，代表询问次数。 

对于每次询问，输入两行： 

第一行输入两个正整数n和x。代表数组的大小，以及小红可以修改成的元素。 

第二行输入n个正整数a_i，代表小红拿到的数组

输出描述

输出 t 行，每行输出一个整数，代表连续子数组的最大和。

# 1

#include <iostream>
#include <vector>
using namespace std;int kadane(const vector<int>& a) {int max_sum = a[0], current_sum = a[0];for (size_t i = 1; i < a.size(); ++i) {current_sum = max(a[i], current_sum + a[i]);max_sum = max(max_sum, current_sum);}return max_sum;
}int main() {int t;cin >> t;while (t--) {int n, x;cin >> n >> x;vector<int> nums(n);for (int i = 0; i < n; i++) {cin >> nums[i];    }int max_original = kadane(nums);int max_with_replacement = max_original;for (int i = 0; i < n; ++i) {int original_value = nums[i];nums[i] = x;max_with_replacement = max(max_with_replacement, kadane(nums));nums[i] = original_value; }cout << max(max_original, max_with_replacement) << endl;}return 0;
}

# 2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int t;cin >> t;while (t--) {int n, x;cin >> n >> x;vector<int> nums(n);for (int i = 0; i < n; i++) {cin >> nums[i];}vector<int> dp1(n), dp2(n);dp1[0] = nums[0];dp2[0] = x;int max_sum = max(dp1[0], dp2[0]);for (int i = 1; i < n; ++i) {dp1[i] = max(nums[i], dp1[i - 1] + nums[i]);dp2[i] = max(x, max(dp2[i - 1] + nums[i], dp1[i - 1] + x));max_sum = max(max_sum, max(dp1[i], dp2[i]));}cout << max_sum << endl;}return 0;
}

• 对于 dp1[i]，要么选择当前元素 nums[i] 作为新的开始，要么延续之前的子数组（dp1[i - 1] + nums[i]）。
• 对于 dp2[i]，有三种选择：
  1. 将当前元素替换为 x，开始新的子数组。
  2. 延续之前已经替换过的子数组（dp2[i - 1] + nums[i]）。
  3. 在此位置进行替换，延续之前未替换的子数组（dp1[i - 1] + x）。

这篇关于0612#连续子数组最大和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---