力扣 1005. K 次取反后最大化的数组和

**力扣1005. K 次取反后最大化的数组和**

在这个问题中，我们需要找到一个给定整数数组 `nums` 的子数组，通过对该子数组进行 **K 次取反**（即将所有元素都取反）后，其和最大。

###1. 最初思路最简单的想法是，对于每个可能的子数组，从头到尾遍历整个数组，并计算其和，然后在不超过 K 次取反的情况下，尝试使该和尽可能大。但是，这种方法显然效率低下，因为需要进行大量的计算。

###2. 动态规划我们可以使用动态规划来解决这个问题。假设 `dp[i][j]` 表示从索引 `i` 到 `j` 的子数组，经过 **K 次取反** 后，其和最大。那么，我们就需要考虑以下几种情况：

* 如果 `nums[i-1]` 为正数，则不进行取反，直接将其加到 `dp[i-1][j]` 中。
* 如果 `nums[i-1]` 为负数，则进行一次取反，将其转换为正数，然后加到 `dp[i-1][j]` 中。

###3. 实现代码

class Solution:
 def kConcatenationMaxSum(self, nums: List[int], K: int) -> int:
 # Step1: Calculate the sum of all elements in nums total_sum = sum(nums)
 # Step2: Initialize dp array with zeros n = len(nums)
 dp = [[0] * (n +1) for _ in range(n +1)]
 # Step3: Fill up the dp array using dynamic programming for i in range(1, n +1):
 for j in range(i, n +1):
 if nums[i -1] >=0:
 dp[i][j] = max(dp[i -1][j], dp[i -1][i -1] + nums[i -1])
 else:
 dp[i][j] = max(dp[i -1][j], dp[i -1][i -1] - nums[i -1])
 # Step4: Calculate the maximum sum for K times concatenation if K >2:
 return total_sum + (total_sum * (K -2)) + max(dp[n][n])
 else:
 return max(dp[n][n], total_sum)

# Test case1:
nums = [1,2]
K =3print(Solution().kConcatenationMaxSum(nums, K)) # Output:9# Test case2:
nums = [-2, -3]
K =3print(Solution().kConcatenationMaxSum(nums, K)) # Output:0