代码随想录算法训练营 Day 24

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 1:
            return 0
            
        n = len(prices)
        diff = [0] * (n - 1)
        for i in range(n - 1):
            diff[i] = prices[i + 1] - prices[i]

        res = 0
        for d in diff:
            if d >= 0:
                res += d
        
        return res

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True
        
        right = 0
        i = 0
        # 根据当前极限距离看是否有可能跳出这个范围
        while i <= right:
            right = max(right, i + nums[i])
            if right >= len(nums) - 1:
                return True
            i += 1
        
        return False

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0

        res = 0
        curr_range = 0
        next_range = 0

        for i in range(len(nums)):
            next_range = max(next_range, i + nums[i])
            if i == curr_range:
                if curr_range != len(nums) - 1:
                    # 遍历已经走到了当前范围最远的地方, 但还没有覆盖到最后位置，需要更新到下一个范围
                    res += 1
                    curr_range = next_range
                    if curr_range >= len(nums) - 1:
                        break
                else:
                    break
        
        return res

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort()
        while k:
            num = nums.pop(0)
            if num < 0:
                nums.append(-num)
                nums.sort()
            else:
                break
            k -= 1
            
        if k == 0:
            return sum(nums)
        elif k % 2 == 1:
            num = -num

        return sum(nums) + num

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort()

        n = len(nums)
        i = 0
        
        while i < n and k > 0:
            if nums[i] < 0:
                nums[i] = -nums[i]
                k -= 1
            i += 1
        
        if k % 2 == 1:
            nums.sort()
            nums[0] = -nums[0]

        return sum(nums)

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort(key=lambda x: abs(x), reverse=True)
        
        for i in range(len(nums)):
            if nums[i] < 0 and k > 0:
                nums[i] = nums[i] * -1
                k -= 1
        
        if k % 2 == 1:
            nums[-1] = -nums[-1]

        return sum(nums)