1
class Solution:
2
    def maxProfit(self, prices: List[int]) -> int:
3
        n = len(prices)
4
        # profit[i] 表示第 i 天和前一天的价格差
5
        profit = [0] * (n - 1)
6

7
        for i in range(1, n):
8
            profit[i - 1] = prices[i] - prices[i - 1]
9

10
        res = 0
11
        # 所有正利润相加即为最大利润（局部最优）
12
        for p in profit:
13
            if p > 0:
14
                res += p
15

16
        return res

1
class Solution:
2
    def canJump(self, nums: List[int]) -> bool:
3
        n = len(nums)
4
        fast = 0  # fast 代表当前能跳到的最远位置
5

6
        for i in range(n - 1):
7
            fast = max(fast, i + nums[i])  # 每步都更新最远可达位置
8
            if fast <= i:
9
                # 当前无法向前跳了，说明陷入死路
10
                return False
11

12
        # 最远能跳到最后一个位置，返回 True
13
        return fast >= n - 1

1
class Solution:
2
    def jump(self, nums: List[int]) -> int:
3
        n = len(nums)
4
        fast = 0  # fast 表示当前能跳到的最远距离
5
        end = 0   # end 表示当前跳跃的边界
6
        res = 0   # res 记录跳跃次数
7

8
        for i in range(n - 1):
9
            fast = max(fast, i + nums[i])  # 不断更新当前最远可达距离
10
            if i == end:
11
                # 到达当前跳跃的终点，必须跳跃一次
12
                res += 1
13
                end = fast  # 更新跳跃边界为当前最远位置
14

15
        return res

1
class Solution:
2
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
3
        # 先对数组按绝对值从大到小排序
4
        nums.sort(key=lambda x: abs(x), reverse=True)
5

6
        for i in range(len(nums)):
7
            # 优先将负数变为正数
8
            if nums[i] < 0 and k > 0:
9
                nums[i] *= -1
10
                k -= 1
11

12
        # 如果还有剩余操作，且为奇数，需要将绝对值最小的数再取反一次
13
        if k % 2 == 1:
14
            nums[-1] *= -1
15

16
        return sum(nums)