[DP题解] 求最大子数组和问题

[DP题解] 求最大子数组和问题

【题目】最大子数组和: 给定一个一维数组，返回子数组的最大累加和。

 * 例如，demo=[1,-2,3,5,-2,6,-1];所有子数组中，

 * [3,5,-2,6]可以累加出最大的和12，所以返回12。

算法分析

完整的JAVA代码如下:

/*
	 * 算法设计（DP算法）
	 * */
	public static int maxSum(int[] demo) {

		int dp[] = new int[demo.length]; 
		int max = demo[0]; 
		dp[0] = demo[0]; 
		for (int i = 1; i < demo.length; i++) {			
			dp[i] = Math.max(dp[i-1] + demo[i] ,demo[i]);
			max = Math.max(max, dp[i]);
		}
		return max;
	}