🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 140+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🌈 小米秋招笔试，来啦！！！

1️⃣ 比较基础的动态规划，大家要争取写出来哦

2️⃣ 双链表模拟题，梦回大一数据结构课程

🌈 01.魔法宝石的能量转换评测链接🔗

问题描述

在一个神秘的魔法世界里，LYA 是一位年轻的魔法师学徒。她正在研究一种特殊的魔法宝石能量转换技术。这种技术可以同时改变相邻两颗宝石的能量极性。

LYA 有一串由 颗魔法宝石组成的项链，每颗宝石都有一个能量值 。她可以进行任意次数的能量转换操作：选择相邻的两颗宝石，同时改变它们的能量极性。也就是说，将第 颗和第 颗宝石的能量值都变为它们的相反数（）。

LYA 的任务是找出经过任意次数（可以是 0 次）的能量转换操作后，能够获得的最大总能量值。她可以根据需要多次选择同一颗宝石进行转换。

输入格式

第一行包含一个整数 ，表示魔法宝石项链的长度。

第二行包含 个整数 ，表示每颗魔法宝石的初始能量值。

输出格式

输出一个整数，表示经过能量转换操作后能获得的最大总能量值。

样例输入1

5
1 -2 3 -4 5

样例输出1

15

样例解释

样例 解释说明

样例1	初始能量总和为 1-2+3-4+5=3。通过选择第二和第三颗宝石进行转换，得到 [1,2,-3,-4,5]，再选择第三和第四颗宝石转换，最终得到 [1,2,3,4,5]，总能量值为 15。

数据范围

• 
• 

题解

动态规划

状态定义： 表示考虑前 个宝石，且第 个宝石的状态为 时的最大能量和

• 有两个值：0 表示第 个宝石保持原状，1 表示第 个宝石被翻转

状态转移:

1. 保持原样时的状态转移： 表示在第 颗宝石保持原样时，能量值可以从前一颗宝石的两种状态（翻转或不翻转）中选择较大的值。

2. 翻转时的状态转移：

最终输出 dp[n][0] 和 dp[n][1] 中的最大值。

参考代码

• Python

class GemEnergy:
    def __init__(self):
        self.gems = []  # 存储宝石能量值
        self.dp = []  # 动态规划数组

    def solve(self):
        n = int(input())  # 读取宝石数量
        self.gems = [0] + list(map(int, input().split()))  # 读取宝石能量值（1-indexed）
        return self.calculate_max_energy(n)  # 计算最大能量和

    def calculate_max_energy(self, n):
        if n == 1:
            return self.gems[1]  # 只有一个宝石的特殊情况

        self.dp = [[0, 0] for _ in range(n + 1)]  # 初始化dp数组
        self.dp[2][0] = self.gems[1] + self.gems[2]  # 初始化：不翻转第二个宝石
        self.dp[2][1] = -self.dp[2][0]  # 初始化：翻转第二个宝石

        for i in range(3, n + 1):
            self.update_dp(i)  # 更新dp数组

        return max(self.dp[n][0], self.dp[n][1])  # 返回最大能量和

    def update_dp(self, i):
        # 不翻转第i个宝石
        self.dp[i][0] = max(self.dp[i-1][0], self.dp[i-1][1]) + self.gems[i]
        # 翻转第i个宝石
        self.dp[i][1] = max(self.dp[i-1][0] - 2*self.gems[i-1], self.dp[i-1][1] + 2*self.gems[i-1]) - self.gems[i]

if __name__ == "__main__":
    solver = GemEnergy()
    print(solver.solve())  # 输出结果

• Java

import java.util.Scanner;

public class GemEnergy {
    private long[] gems;  // 存储宝石能量值
    private long[][] dp;  // 动态规划数组

    public long solve() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 读取宝石数量
        gems = new long[n + 1];  // 初始化宝石数组（1-indexed）
        for (int i = 1; i <= n; i++) {
            gems[i] = scanner.nextLong();  // 读取每个宝石的能量值
        }
        return calculateMaxEnergy(n);  // 计算最大能量和
    }

    private long calculateMaxEnergy(int n) {
        if (n == 1) return gems[1];  // 只有一个宝石的特殊情况

        dp = new long[n + 1][2];  // 初始化dp数组
        dp[2][0] = gems[1] + gems[2];  // 初始化：不翻转第二个宝石
        dp[2][1] = -dp[2][0];  // 初始化：翻转第二个宝石

        for (int i = 3; i <= n; i++) {
            updateDP(i);  // 更新dp数组
        }

        return Math.max(dp[n][0], dp[n][1]);  // 返回最大能量和
    }

    private void updateDP(int i) {
        // 不翻转第i个宝石
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]) + gems[i];
        // 翻转第i个宝石
        dp[i][1] = Math.max(dp[i-1][0] - 2*gems[i-1], dp[i-1][1] + 2*gems[i-1]) - gems[i];
    }

    public static void main(String[] args) {
        GemEnergy solver = new GemEnergy();
        System.out.println(solver.solve());  // 输出结果
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>

using ll = long long;

class GemEnergy {
private:
    std::vector<ll> gems;  // 存储宝石能量值
    std::vector<std::vector<ll>> dp;  // 动态规划数组

public:
    ll solve() {