算法修炼30、连续子数组的最大和

 题目描述&＃xff1a;

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

  解题思路&＃xff1a;

  本题可以看做是一个多阶段决策找最优解的问题&＃xff0c;因此可以用典型的动态规划思想来求解。用 res[ i ] 表示以第 i 个元素结尾的子数组的最大和&＃xff0c;那么有以下递推公式&＃xff1a;res[ i ]&＃61;max(res[ i-1]&＃43;data[ i ],data[ i ]).

  这个公式的含义是&＃xff1a;当以第i-1个数字结尾的子数组中所有数字的和小于0时&＃xff0c;把这个负数与第i个数累加&＃xff0c;则得到的和比第i个数字本身还要小&＃xff0c;所以这种情况下res[ i ]就是第i个数字本身。反之&＃xff0c;如果以第i-1个数字结尾的子数组中所有数字的和大于0&＃xff0c;则与第i个数字累加就得到以第i个数字结尾的子数组中所有数字的和。

  举例&＃xff1a;

  编程实现&＃xff08;Java&＃xff09;&＃xff1a;

public int FindGreatestSumOfSubArray(int[] array) {/*动态规划&＃xff0c;用res[i]表示以第i个元素结尾的最大和res[i]中最大者即为最大连续子序列的和*/if(array&＃61;&＃61;null||array.length&＃61;&＃61;0)return Integer.MIN_VALUE;int endAsI&＃61;array[0];int result&＃61;endAsI;for(int i&＃61;1;iarray[i]? endAsI&＃43;array[i] : array[i];if(endAsI>result)result&＃61;endAsI;}return result;}