摘要
Title: 100337. 最大化子数组的总成本
Tag: dp，状态机
Memory Limit: 64 MB
Time Limit: 1000 ms

100337. 最大化子数组的总成本

题意

给你一个长度为 n 的整数数组 nums。

子数组 nums[l…r]（其中 0 <= l <= r < n）的成本定义为：

cost(l, r) = nums[l] - nums[l + 1] + … + nums[r] * (−1)r − l

你的任务是将 nums 分割成若干子数组，使得所有子数组的成本之和最大化，并确保每个元素正好属于一个子数组。

具体来说，如果 nums 被分割成 k 个子数组，且分割点为索引 i1, i2, …, ik − 1（其中 0 <= i1 < i2 < … < ik - 1 < n - 1），则总成本为：

cost(0, i1) + cost(i1 + 1, i2) + … + cost(ik − 1 + 1, n − 1)

返回在最优分割方式下的子数组成本之和的最大值。

注意：如果 nums 没有被分割，即 k = 1，则总成本即为 cost(0, n - 1)。

思路

转化一下题意：
给 nums 的每个元素前面加上正负号，其中正号可以任意添加（因为可以视为一个子数组的开头），负号元素只能紧接在正号元素后面。求最大和。也就是说把负号改成正号，但是不能同时修改相邻的两个负数。

那么就可以当做状态机一步一步往后推，dp[i][1 / 0] 代表表示第 i 个元素是正（j=0）或负（j=1）号元素的最大前缀和，正的时候可以由前面推过来，负的只能由正的推过来

代码

'''
Author: NEFU AB-IN
Date: 2024-06-23 16:46:42
FilePath: \LeetCode\100337\100337.py
LastEditTime: 2024-06-23 16:49:37
'''
# import
from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, gcd, sqrt, fabs, ceil, floor
from types import GeneratorType
from typing import TypeVar, List, Dict, Any, Callable


# Data structure
class SA:

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __lt__(self, other):
        return self.x < other.x


# Constants
N = int(2e5 + 10)  # If using AR, modify accordingly
M = 20
INF = int(2e9)

# Set recursion limit
setrecursionlimit(INF)

# Read
input = lambda: stdin.readline().rstrip("\r\n")  # Remove when Mutiple data
read = lambda: map(int, input().split())
read_list = lambda: list(map(int, input().split()))


# Func
class std:

    # Recursion
    @staticmethod
    def bootstrap(f, stack=None):
        if stack is None:
            stack = []

        def wrappedfunc(*args, **kwargs):
            if stack:
                return f(*args, **kwargs)
            else:
                to = f(*args, **kwargs)
                while True:
                    if isinstance(to, GeneratorType):
                        stack.append(to)
                        to = next(to)
                    else:
                        stack.pop()
                        if not stack:
                            break
                        to = stack[-1].send(to)
                return to

        return wrappedfunc

    letter_to_num = staticmethod(lambda x: ord(x.upper()) - 65)  # A -> 0
    num_to_letter = staticmethod(lambda x: ascii_uppercase[x])  # 0 -> A
    array = staticmethod(lambda x=0, size=N: [x] * size)
    array2d = staticmethod(
        lambda x=0, rows=N, cols=M: [std.array(x, cols) for _ in range(rows)])
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)
    filter = staticmethod(lambda func, iterable: list(filter(func, iterable)))


# —————————————————————Division line ——————————————————————


class Solution:

    def maximumTotalCost(self, nums: List[int]) -> int:
        n = len(nums)
        dp = std.array2d(-INF, n, 2)

        dp[0][0] = nums[0]
        for i in range(1, n):
            dp[i][0] = std.max(dp[i - 1][0], dp[i - 1][1]) + nums[i]
            dp[i][1] = dp[i - 1][0] - nums[i]

        return std.max(dp[n - 1][0], dp[n - 1][1])