DP动态规划基础题（Kadane算法）
动态规划（Dynamic Programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学等领域中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划算法通常用于优化问题，特别是那些具有重叠子问题和最优子结构性质的问题。
动态规划的基本思想
重叠子问题：动态规划算法中，问题被分解成多个子问题，而这些子问题会重复出现多次。如果这些子问题的结果可以被保存下来，那么当它们再次出现时，可以直接使用之前的结果，而不需要重新计算。
最优子结构：一个问题的最优解包含其子问题的最优解。这意味着，如果我们能够找到所有子问题的最优解，那么就能构造出原问题的最优解。
动态规划的步骤
定义状态：确定dp数组（或dp表）中的状态表示什么。通常，状态是问题规模的一个或多个参数。
确定状态转移方程：找出状态之间的关系，即如何从一个或多个较小子问题的解构造出当前问题的解。
确定初始状态和边界条件：确定dp数组的初始值，以及问题的边界条件。
计算顺序：确定如何迭代地填充dp数组，通常从小到大或从上到下。
构造最优解：一旦dp数组被填充，就可以通过它来构造问题的最优解。
动态规划的简单例子
斐波那契数列：计算第n个斐波那契数，其中斐波那契数列定义为：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)。
状态：dp[i] 表示第i个斐波那契数。
状态转移方程：dp[i] = dp[i-1] + dp[i-2]。
初始状态和边界条件：dp[0] = 0, dp[1] = 1。
计算顺序：从i = 2到n，依次计算dp[i]。
通过动态规划，我们可以避免重复计算子问题，从而提高算法的效率。动态规划适用于许多问题，如背包问题、最长公共子序列问题、最短路径问题等。
翻转增益的最大子数组和 -
链接: 翻转增益的最大子数组和
题目：
问题描述
给定整数数组，我们称其中连续的 0 个或多个整数为一个子数组，求翻转任一子数组后，新数组中子数组的和的最大值
输入格式
第一行输入为 N，代表数组长度
第二行输入为 N 个整数，依次为数组的每个元素
输出格式
一个整数 K，代表所有可能新数组中子数组的和的最大值
输入样例
5
1 2 3 -1 4
输出样例
10
说明
选择翻转子数组 [-1, 4] 或 [1, 2, 3, -1]，新数组分别是 [1, 2, 3, 4, -1] 和 [-1, 3, 2, 1, 4]，二者的子数组最大和都是 10
数据范围
50% case：1 <= N <= 100, -100<= arr[i] <= 100
100% case：1 <= N <= 1e6, -100<= arr[i] <= 100
思路：
问题理解
给定一个整数数组，我们可以翻转任意一个子数组（即子数组中的元素顺序颠倒），然后计算新数组中所有子数组的和的最大值。
解题思路
初始子数组和：
首先，计算原始数组中所有子数组的和的最大值。这可以通过Kadane算法来实现。
翻转子数组的影响：
翻转一个子数组会影响该子数组及其周围的子数组的和。我们需要找到一个翻转子数组的方式，使得新数组中子数组的和最大。
计算翻转后的最大子数组和：
对于每个可能的翻转子数组，计算翻转后的新数组中所有子数组的和的最大值。
选择所有可能翻转子数组中，使得新数组中子数组和最大的那个。
关键步骤
Kadane算法：
使用Kadane算法计算原始数组的最大子数组和。
翻转子数组的影响：
对于每个可能的翻转子数组，计算翻转后的新数组中所有子数组的和的最大值。
这可以通过计算翻转子数组的前后部分的最大子数组和来实现。
综合考虑：
综合考虑原始数组的最大子数组和以及所有可能翻转子数组后的最大子数组和，选择最大的那个作为最终答案
Kadane算法是一种用于求解最大子数组和的经典算法。它的核心思想是通过动态规划来逐步计算当前子数组的和，并记录最大子数组的和。
Kadane算法的工作原理
初始化：
初始化两个变量：maxEndingHere 和 maxSoFar。
maxEndingHere 表示以当前元素结尾的最大子数组和。
maxSoFar 表示全局的最大子数组和。
遍历数组：
从数组的第一个元素开始遍历，逐步更新 maxEndingHere 和 maxSoFar。
对于每个元素 array[i]，更新 maxEndingHere 为 max(array[i], maxEndingHere + array[i])。
这意味着如果当前元素 array[i] 比 maxEndingHere + array[i] 大，则从当前元素开始重新计算子数组和。
更新 maxSoFar 为 max(maxSoFar, maxEndingHere)。
这意味着记录全局的最大子数组和。
返回结果：
遍历结束后，maxSoFar 即为最大子数组和。
private static int kadane(int[] array) {
int maxEndingHere = array[0];
int maxSoFar = array[0];
for (int i = 1; i < array.length; i++) {
maxEndingHere = Math.max(array[i], maxEndingHere + array[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
通过代码：
java 代码解读复制代码public class Main {
public static int solution(int N, int[] data_array) {
// 计算原始数组的最大子数组和
int originalMaxSum = kadane(data_array);
// 计算翻转子数组后的最大子数组和
int maxSumAfterFlip = originalMaxSum;
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
// 翻转子数组 [i, j]
int[] flippedArray = flipSubarray(data_array, i, j);
// 计算翻转后的最大子数组和
int flippedMaxSum = kadane(flippedArray);
// 更新最大值
maxSumAfterFlip = Math.max(maxSumAfterFlip, flippedMaxSum);
}
}
return maxSumAfterFlip;
}
// Kadane算法计算最大子数组和
private static int kadane(int[] array) {
int maxEndingHere = array[0];
int maxSoFar = array[0];
for (int i = 1; i < array.length; i++) {
maxEndingHere = Math.max(array[i], maxEndingHere + array[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
// 翻转子数组 [start, end]
private static int[] flipSubarray(int[] array, int start, int end) {
int[] flippedArray = array.clone();
while (start < end) {
int temp = flippedArray[start];
flippedArray[start] = flippedArray[end];
flippedArray[end] = temp;
start++;
end--;
}
return flippedArray;
}
public static void main(String[] args) {
// 测试用例
int N = 4;
int[] data_array = {-3, -1, -2, 3};
System.out.println(solution(N, data_array)); // 预期输出: 3
}
}
。