动态规划题解
子数组的最大累加和问题
http://www.nowcoder.com/questionTerminal/554aa508dd5d4fefbf0f86e5fe953abd
动态规划
这是一个典型的动态规划问题。
最优子结构
在自下而上的递推过程中,我们求得的每个子问题一定是全局最优解,既然它分解的子问题是全局最优解,那么依赖于它们解的原问题自然也是全局最优解。
重复子问题
递归地寻找子问题的最优解时,子问题会重叠地出现在子问题里,会有很多重复的计算,动态规划可以保证每个重叠的子问题只会被求解一次。
动态规划解题步骤:
- 定义子问题
- 写出子问题的递推关系
- 确定DP数组的计算顺序
本题中的具体表现为:
dp[i] 以i为结尾的最大和 dp[i] = Math.max(dp[i], dp[i - 1] + arr[i]); dp[0] = arr[0]; max = Math.max(dp[i]);
题解:
import java.util.*; public class Solution { /** * max sum of the subarray * @param arr int整型一维数组 the array * @return int整型 */ public int maxsumofSubarray (int[] arr) { // write code here int len = arr.length; int res = arr[0]; //最优解 int dp = arr[0]; //自底而上解子问题 for(int i = 1; i < len; i++){ dp = Math.max(arr[i], dp + arr[i]); res = Math.max(dp, res); } return res; } }