2025-01-26：最大化子数组的总成本。用go语言，给定一个包含 n 个整数的数组 nums，定义数组中某个区间的成本为该区

福大大架构师每日一题

发布于 2025-02-05 14:03:09

4700

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2025-01-26：最大化子数组的总成本。用go语言，给定一个包含 n 个整数的数组 nums，定义数组中某个区间的成本为该区间的第一个数减去最后一个数，之后第二个数加上倒数第二个数，以此类推，直到最后一个数的符号为负。

任务是将数组 nums 划分成若干个子数组，使得所有子数组的成本之和达到最大值，并确保每个数字仅属于一个子数组。

设将 nums 分成 k 个子数组，分割点为索引 i1, i2, ..., ik − 1，则总成本为每个相邻区间的成本之和。

要求计算在最优分割下的子数组成本之和的最大值。

1 <= nums.length <= 100000。

-1000000000 <= nums[i] <= 1000000000。

输入： nums = [1,-2,3,4]。

输出： 10。

解释：

一种总成本最大化的方法是将 [1, -2, 3, 4] 分割成子数组 [1, -2, 3] 和 [4]。总成本为 (1 + 2 + 3) + 4 = 10。

答案2025-01-26：

chatgpt[1]

题目来自leetcode3196。

大体步骤如下：

1.定义两个变量 f0 和 f1 初始值为 0，用于表示当前位置元素被分到不同子数组时的成本和。f0 用于记录分到当前位置的元素的总成本，f1 用于记录分到当前位置元素后的最佳成本。

2.从数组的最后一个元素开始向前遍历：

2.a.计算当前位置的 f0 和 f1。对于 f0，表示当前位置元素被分到当前子数组的成本；对于 f1，表示当前位置元素被分到不同子数组时的最佳成本。

2.b.f0 更新为 f1 加上当前位置元素的值，表示如果当前位置元素被分到当前子数组，更新总成本。

2.c.f1 更新为 f1 加上当前位置元素的值和 f0 减去当前位置元素的值的较大值，表示决定当前位置元素分到当前子数组还是另起一个子数组，以获得最佳成本。

3.最终返回 f0 的值作为结果，即最优分割下的子数组成本之和的最大值。

总的时间复杂度为 O(n)，其中 n 为数组的长度，因为需要遍历整个数组。

总的额外空间复杂度为 O(1)，因为只需要常数级别的额外空间来存储 f0 和 f1。

Go完整代码如下：

package main

import (
    "fmt"
)

func maximumTotalCost(a []int)int64 {
    f0, f1 := 0, 0
    for i := len(a) - 1; i >= 0; i-- {
        f0, f1 = f1+a[i], max(f1+a[i], f0-a[i])
    }
    returnint64(f0)
}

func main() {
    nums := []int{1,-2,3,4}
    result := maximumTotalCost(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

defmaximum_total_cost(a):
    f0, f1 = 0, 0
    for num inreversed(a):
        f0, f1 = f1 + num, max(f1 + num, f0 - num)
    return f0

defmain():
    nums = [1, -2, 3, 4]
    result = maximum_total_cost(nums)
    print(result)

if __name__ == "__main__":
    main()

Solidity完整代码如下：

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

contract MaximumTotalCost {
    
    functionmaximumTotalCost(int256[] memory a) public pure returns (int256) {
        int256 f0 = 0;
        int256 f1 = 0;

        for (uint256 i = a.length; i > 0; i--) {
            int256 num = a[i - 1]; // 获取当前数组元素，注意下标从 0 开始
            (f0, f1) = (f1 + num, max(f1 + num, f0 - num));
        }
        
        return f0;
    }

    functionmax(int256 a, int256 b) internal pure returns (int256) {
        return a > b ? a : b;
    }
}