T20744: 土豪购物

dp, http://cs101.openjudge.cn/practice/20744/

给一个整数组成的数列，其中每个数字代表商品价值(可能为负)

土豪买东西的方法是 "从第n个到第k个商品我全要了!!!" (n<=k)，

换句话说土豪一定会买下连续的几个商品

买完以后土豪会看心情最多放回去其中一个商品(可以不放回)

但土豪不能空手而归，他至少要带回去一个商品

请问聪明的(?)土豪可以买到最大价值总和为多少的商品?

样例:

商品价值:1,-5,0,3 输出:4 最大价值总和是买[1,-5,0,3]，并放回-5后的总和

商品价值:-2,-2,-2 输出:-2 最大价值总和是买[-2]，不放回的总和(至少要带回去一个商品)

输入

一个逗号分隔，由整数组成的商品价值

输出

一个整数

样例输入

1,-5,0,3

样例输出

提示

最大价值总和是买[1,-5,0,3]，并放回-5后的总和

定义多个dp数组。类似于 1195C. Basketball Exercise, dp, 1400, https://codeforces.com/problemset/problem/1195/C ，25573: 红蓝玫瑰，dp, greedy, http://cs101.openjudge.cn/practice/25573/

python

a = list(map(int, input().split(',')))
dp1 = [0] * len(a);
dp2 = [0] * len(a)
dp1[0] = a[0];
dp2[0] = a[0]
for i in range(1, len(a)):
    dp1[i] = max(dp1[i - 1] + a[i], a[i])
    dp2[i] = max(dp1[i - 1], dp2[i - 1] + a[i], a[i])
print(max(dp2))

这个问题可以用动态规划（Dynamic Programming, DP）来解决，通过设计两个 DP 数组，我们可以高效地计算出土豪购买商品的最大价值总和。
以下是问题解读和代码逻辑的详细说明：
问题分析
土豪需要购买连续的一段商品，且他最多可以放回去其中一个商品，但至少要购买一个商品。为了求得最大价值总和，我们需要处理两种情况：
不放回任何商品：直接计算出某一段商品的连续子数组和。
放回一个商品：在计算连续子数组和的同时，尝试从中移除一个商品，观察是否能够使总和更大。
解法设计
使用两个 DP 数组分别处理上述两种情况：
dp1[i] 表示 以第 i 个商品结尾的连续子数组最大和，不考虑放回商品。
状态转移公式：dp1[i] = max(dp1[i - 1] + a[i], a[i])
解释：当前商品 a[i] 要么加入之前的子数组，要么单独成为一个新的子数组。
dp2[i] 表示 以第 i 个商品结尾的连续子数组最大和，允许放回其中一个商品。
状态转移公式：dp2[i] = max(dp1[i - 1], dp2[i - 1] + a[i], a[i])
解释：
dp1[i - 1] 表示选择前面的子数组，但不加当前商品。
dp2[i - 1] + a[i] 表示当前商品加入到之前可能已经放回一个商品的子数组。
a[i] 表示单独选择当前商品。
最终答案是 dp2 数组中的最大值。因为 dp2 考虑了放回一个商品的情况，所以它能提供最大的可能价值。
时间复杂度
时间复杂度: O(n)，因为只需要线性遍历数组一次。
空间复杂度: O(n)（可以进一步优化到 O(1)）。
关键点总结
dp1 用于计算不放回商品时的最大和。
dp2 在 dp1 的基础上扩展，允许放回一个商品。
土豪不能空手而归，因此需要注意初始条件设置和最终答案选择。

好巧妙的解法，构造两个数组，一个都不放回，一个允许放回一次。这个思路可以多学习一下。在答案的基础上把空间复杂度优化到O(n)

python

# 俞天麒 24物理学院
a=list(map(int,input().split(",")))
n=len(a)
dp1,dp2=a[0],a[0]
ans=0
for i in range(1,n):
    dp1,dp2=max(a[i],dp1+a[i]),max(dp1,dp2+a[i])
    ans=max(ans,dp2)
print(ans)

需要考虑两种情况：

不放回商品时的最大连续子数组和（Kadane算法）。
放回一个商品时的最大连续子数组和。

由于我们可以选择放回任何一个商品，因此需要考虑放回每一个商品对最大连续子数组和的影响。我们可以通过两次遍历数组来解决这个问题：

第一次遍历从左到右计算以每个元素结尾的最大子数组和。
第二次遍历从右到左计算以每个元素开始的最大子数组和。

然后，我们遍历数组，对于每个位置，我们尝试放回该位置的商品，并检查如果放回这个商品后，左边子序列的最大和加上右边子序列的最大和是否会比当前的最大值还要大。

python

def kadane(nums):
    max_ending_here = max_so_far = nums[0]
    for x in nums[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

def max_sum_shopping(values):
    # 不放回商品的情况下的最大价值总和
    max_without_deletion = kadane(values)

    # 如果整个数列的和都是负的，则土豪只能选择一个价值最大的商品
    if max_without_deletion < 0:
        return max(values)

    # 准备两个数组来存储从左到右和从右到左的最大子数组和
    left_max_sums = [0] * len(values)
    right_max_sums = [0] * len(values)

    # 从左到右的最大子数组和
    current = 0
    for i in range(len(values)):
        current = max(0, current + values[i])
        left_max_sums[i] = current

    # 从右到左的最大子数组和
    current = 0
    for i in range(len(values) - 1, -1, -1):
        current = max(0, current + values[i])
        right_max_sums[i] = current

    # 放回一个商品时的最大价值总和
    max_with_deletion = 0
    for i in range(1, len(values) - 1):
        max_with_deletion = max(max_with_deletion, left_max_sums[i - 1] + right_max_sums[i + 1])

    # 返回放回一个商品和不放回一个商品两种情况下的最大价值
    return max(max_with_deletion, max_without_deletion)

# 读取输入并处理
values_str = input().strip()
values = list(map(int, values_str.split(',')))
print(max_sum_shopping(values))

思路：遍历所有的商品，更新最小值，当前和加上现在遍历的商品，在已获得的最大值、当前和、当前和减去最小值三个量之间更新已获得的最大值，如果当前和小于0，说明前面的所有商品加入考虑也不会得到更优的情况，于是重新开始，重置当前和和最小值，最后输出最大值。

python

# 张清州 24化学与分子工程学院
items = list(map(int, input().split(',')))
n = len(items)
max_sum = float('-inf')
current_sum = 0
min_element = float('inf')
for i in range(n):
    current_sum += items[i]
    min_element = min(min_element, items[i])
    max_sum = max(max_sum, current_sum, current_sum - min_element)
    if current_sum < 0:
        current_sum = 0
        min_element = float('inf')
print(max_sum)

M20744: 土豪购物，这是 Kadane's Algorithm 变形啊。另外，E22548: 机智的股⺠老张，感觉也是变形。

T20744: 土豪购物 ​

T20744: 土豪购物