连续子数组的最大和.md

武培轩 2020年02月06日 74次浏览

题目描述

在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?

例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。(子向量的长度至少是1)

思路

遍历array,对于每一个数字,我们判断,(之前的sum + 这个数字) 和 (这个数字) 比大小,如果(这个数字)自己就比 (之前的sum + 这个数字) 大的话,那么说明不需要再继续加了,直接从这个数字,开始继续,因为它自己已经比之前的sum都大了。

反过来,如果 (之前的sum + 这个数字)大于 (这个数字)就继续加下去。

利用动态规划做题。
只遍历数组一遍,当从头到尾部遍历数组A, 遇到一个数有两种选择 (1)加入之前subArray (2)自己另起一个subArray

设状态F[i], 表示以array[i]结尾的最大连续子序列和,状态转移方程如下:

F[i] = max(F[i-1] + array[i],array[i])

从状态转移方程上F[i]只与F[i-1]有关,与其他都无关,因此可以用一个变量来记住前一个的最大连续数组和就可以了。这样就可以节省空间了。

代码实现

package Array;

/**
 * 连续子数组的最大和
 * 在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?
 * 例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。(子向量的长度至少是1)
 * 思路:
 *   F(i):以array[i]为末尾元素的子数组的和的最大值,子数组的元素的相对位置不变
     F(i)=max(F(i-1)+array[i] , array[i])
     res:所有子数组的和的最大值
     res=max(res,F(i))
     如数组[6, -3, -2, 7, -15, 1, 2, 2]
     初始状态:
     F(0)=6
     res=6
     i=1:
     F(1)=max(F(0)-3,-3)=max(6-3,3)=3
     res=max(F(1),res)=max(3,6)=6
     i=2:
     F(2)=max(F(1)-2,-2)=max(3-2,-2)=1
     res=max(F(2),res)=max(1,6)=6
     i=3:
     F(3)=max(F(2)+7,7)=max(1+7,7)=8
     res=max(F(2),res)=max(8,6)=8
     i=4:
     F(4)=max(F(3)-15,-15)=max(8-15,-15)=-7
     res=max(F(4),res)=max(-7,8)=8
     以此类推
     最终res的值为8
 */

public class Solution01 {
    public static void main(String[] args) {
        int[] arr = {6,-3,-2,7,-15,1,2,2};
        System.out.println(FindGreatestSumOfSubArray(arr));
    }
    public static int FindGreatestSumOfSubArray(int[] array) {
        if(array.length==0)
            return 0;
        int sum = array[0];//保存每组的和
        int maxSum = array[0];//连续子数组最大和
        //动态规划
        for(int i = 1;i<array.length;i++){
            sum = Math.max(sum+array[i],array[i]);
            maxSum = Math.max(sum,maxSum);
        }
        return maxSum;
    }
}