数组之连续子数组的最大和【时间效率】

1.本题知识点

   数组，时间效率

2. 题目描述

  给一个整型数组，有正有负，数组中的一个或连续多个组成子序列，返回所有连续子序列中和的最大值。例如:{6,-3,-2,7,-15,1,2,2},连续子序列和的最大值为8。

3.解题思路

   ① 定义状态转移方程

    以array[i]结尾的子序列的和的最大值：

    F（i）= max（F（i-1）+array[i] ， array[i]）

   ② 求解原问题

    初始状态为F(0)，下一个状态为通过①的方程计算得到 F(1)，依次递推，最终求得所有连续子序列的和的最大值

   Java版本：

static int findMaxSubArray(int[] array) throws Exception{
		if(array.length < 0 )
		{
			throw new Exception("params error ...");
		}

		//初始状态，因为要通过递推公式从左往右递推
        int subProblemAnswer = array[0];   
        //记录原问题的解：当前所有子数组的和的最大值
        int maxN = subProblemAnswer;   
        for (int i = 1; i < array.length; i++)
        {
        	//1.求解子问题(通过递推公式求) ====> 定义状态转移方程：以array[i]结尾的连续数组最大值
        	subProblemAnswer = Math.max(subProblemAnswer+array[i], array[i]); 
        	//2.求解原问题：所有子序列的和的最大值
        	maxN = Math.max(subProblemAnswer, maxN); 
        }
        
        return maxN;
	}