网站规划要点/seo好学吗

题目描述

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).
输入：[1,-2,3,10,-4,7,2,-5]
返回值：18
说明：输入的数组为{1,-2,3,10,—4,7,2,一5}，和最大的子数组为{3,10,一4,7,2}，因此输出为该子数组的和 18。

参考博客

动态规划

使用动态规划来求解，需要一个表格数组dp存储累加和，以及一个变量res存储最优值，从头遍历数组，即从子问题开始，不断将问题规模扩大，同时利用已经求解的子问题来求解新的问题。

当子问题的累加和dp[i-1]加上当前数组的值arr[i]小于当前数组值arr[i]时，说明之前的累加和为负数了，则没必要与之前的子数组继续累加，因此当以arr[i]结尾时，累加和为dp[i]=arr[i]，即抛弃之前的累加和，重新开始累加；反之dp[i-1] + arr[i] > arr[i]则表明之前的累加和不是负数，可以继续累加，但是现在不一定是累加和最大的时候，因为arr[i]可能是个负数，但是它后面可能存在更大的正数，我们不能就从这里断开了，还需要继续累加，所以累加完后要判断当前的累加和是否比历史的最优值res更大，是则更新。

扩展，在动态规划的同时记录累加和最大的连续子数组
我们可以使用一个数组record来记录最优值的解，即最大连续子数组，用-1代表当前位置为连续子数组的开头，并且用一个变量max_idx来记录最大连续子数组的结尾，当求解完后只需从max_idx开始往回找到第一个-1的位置即可找到最优连续子数组。record的更新方法是：当dp[i-1]<0时，表明前面的累加和是负数，此时没必要继续累加，重新开一个子数组，此时record[i] = -1，否则继续累加，record[i] = 1。并且更新最优解res时，顺便更新最优子数组的结尾下表max_idx为当前位置

public class Solution {public int FindGreatestSumOfSubArray(int[] array) {int len = array.length, res;int[] dp = new int[len];int[] record = new int[len];res = dp[0] = array[0];record[0] = -1; // 表示最大子数组从-1的地方开始int max_idx = 0; // 记录最大连续子数组的结尾下标for (int i = 1; i < len; i++) {if (dp[i - 1] < 0) {// 前面的小于0 抛弃掉dp[i] = array[i];record[i] = -1; // 重新开始连续子数组} else {// 可以继续累加dp[i] = dp[i - 1] + array[i];record[i] = 1;}// 与历史最好的比较if (dp[i] > res) {// 如果比历史值更好, 则更新历史最好值, 并记录下标位置res = dp[i];max_idx = i;}}// 输出最好结果int tmp_idx = max_idx;while (tmp_idx > 0 && record[tmp_idx] != -1)tmp_idx--;for (int i = tmp_idx; i <= max_idx; i++)System.out.print(array[i] + " ");return res;}public static void main(String[] args) {int[] arr = {1, -2, 3, 10, -4, 7, 2, -5};new Solution().FindGreatestSumOfSubArray(arr);}
}

数组法

这种方法其实和DP是一样的，只是它不需要类似DP的填表过程，因为这题没有要求记录最大和的解（即由哪几个数组成最大子数组），所以不填表也可以。同样使用res来记录到当前为止最大的连续子数组的和，使用acc_sum来记录到当前为止能累积的数组的和（不一定是最大的，只是说明能继续累积下去的数组的和），如果acc_sum<0，则可以抛弃掉，因为它是负数了，没必要再加上它，让acc_sum等于当前位置的数重新开始累积，否则acc_sum还可以继续累加下去，即使当前位置的数是一个负数也可以累加，因为这个数的后面可能是一个更大的正数，所以前面说了acc_sum并不一定是最大的。如果acc_sum>res，则更新res，说明累加到现在有更好的值。

public class Solution {public int FindGreatestSumOfSubArray(int[] array) {int len = array.length, res = array[0];int acc_sum = array[0];for (int i = 1; i < len; i++) {if (acc_sum < 0)// 重新开始acc_sum = array[i];else// 可以继续累加acc_sum += array[i];if (acc_sum > res)res = acc_sum;}return res;}
}