来自牛客剑指offer

问题描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

问题思路

我认为可以理解为01背包问题较为简洁的写法是使用动态规划，所谓动态规划就是记录每次操作的中间值，即利用空间的浪费来换取时间的效率的提升对于拿到的一个数，我们需要记录放入后的值和未放入的值（即所求的最大连续子串的和）如果之前的数加上当前的数大于当前的数，那么我们就加上如果小于的话，那么我们为什么不直接从当前数开始呢？为什么还要带上之前的结果（反而会变小）

Code

//简单思路，无优化 //2层循环，时间复杂度为O(n*logn) public int FindGreatestSumOfSubArray(int[] array) { int maxVal = array[0]; int index = 0; while (index < array.length) { if (array[index] <= 0) { maxVal = maxVal > array[index] ? maxVal : array[index]; index++; continue; } int sum = 0; int count = index; while (count < array.length) { System.out.println("sum="+sum); maxVal = maxVal > sum ? maxVal : sum; System.out.println("m="+maxVal); int temp = sum + array[count++]; if (temp < 0) break; else sum = temp; } maxVal = maxVal > sum ? maxVal : sum; index++; } return maxVal; } //DP思路 public class Solution { public int FindGreatestSumOfSubArray(int[] array) { int maxVal = Integer.MIN_VALUE; int[] tempVal = new int[array.length]; tempVal[0] = array[0]; for (int i = 1; i < array.length; i++) { // 如果之前的数加上当前的数大于当前的数，那么我们就加上 tempVal[i] = Math.max(tempVal[i-1] + array[i],array[i]); maxVal = Math.max(tempVal[i],maxVal); } return maxVal; } }