数据结构与算法-子数组的最大累加和

vlambda
2021-01-26

数据结构与算法-子数组的最大累加和

题目描述：

给定一个数组arr，返回子数组的最大累加和

例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.

题目保证没有全为负数的数据

[要求]

时间复杂度为O(N) O(n) ，空间复杂度为O(1);

解题思路：

1. 暴力破解法；

2. 动态规划-状态转移方程如下：

dp[i] = arr[i]; dp[i-1]><=0

dp[i] = dp[i-1] + arr[i]; dp[i-1]>0

实现代码：

/** * 子数组的最大累加和 * 给定一个数组arr，返回子数组的最大累加和 * 例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12. * 题目保证没有全为负数的数据 * [要求] * 时间复杂度为O(n)O(n)，空间复杂度为O(1)O(1) */public class MaxSumOfSubarray { /** * max sum of the subarray * @param arr int整型一维数组 the array * @return int整型 * * 暴力破解： * tmp = arr[i]+arr[i+1]+arr[i+2]+......+arr[j] ;0=<i<j<length * tmp = arr[i]; i=j */ public static int maxsumofSubarray (int[] arr) { // write code here if (arr.length==0){ return 0; } if (arr.length==1){ return arr[0]; } int length = arr.length; int maxSum = Integer.MIN_VALUE; for (int i = 0; i<length; i++){ for (int j=i;j<length; j++){ int tmp=0; if (i==j){ tmp = arr[i]; }else{ for (int k=i; k<=j; k++){ tmp +=arr[k]; } } maxSum = Math.max(maxSum,tmp); } } return maxSum; }
 /** *max sum of the subarray * @param arr int整型一维数组 the array * @return int整型 * * 动态规划-状态转移方程： *dp[i] = dp[i-1] + arr[i]; dp[i-1]>0 *dp[i] = arr[i]; dp[i-1]><=0 */ public static int maxsumofSubarrayByDp(int[] arr){ if (arr.length==0){ return 0; } if (arr.length==1){ return arr[0]; } int length = arr.length; int maxSum = Integer.MIN_VALUE; int[] dp = new int[length]; for (int i=0; i<length; i++){ if (i==0){ dp[i] = arr[i]; }else if (dp[i-1]<=0){ dp[i] = arr[i]; }else { dp[i] = dp[i-1] + arr[i]; } maxSum = Math.max(dp[i],maxSum); } return maxSum; }
 public static void main(String[] args){ int[] arr = new int[]{1, -2, 3, 5, -2, 6, -1}; int res = maxsumofSubarrayByDp(arr); System.out.println(res); }}

针对动态规划转移方程，用迭代中间变量方式做空间优化，代码实现如下：

 /** *max sum of the subarray * @param arr int整型一维数组 the array * @return int整型 * * 一元迭代 */ public static int maxsumofSubarrayByIterator(int[] arr){ if (arr.length==0){ return 0; } if (arr.length==1){ return arr[0]; } int length = arr.length; int maxSum = Integer.MIN_VALUE; int cur = Integer.MIN_VALUE; int iter = arr[0]; for (int i=1; i<length; i++){ if (iter<=0){ cur = arr[i]; }else { cur = iter + arr[i]; } iter = cur; maxSum = Math.max(cur,maxSum); } return maxSum;    }