动态规划求解连续子数组的最大和

给定一个整数数组，数组里有正有负。数组中的一个活连续多个元素组成一个子数组。求所有子数组的和的最大值。
一、枚举所有可能——最基础的解法
最直观的解法就是，计算出所有可能组合的子数组的和，返回最大的和。这种解法的复杂度最低也要$O(n)$O(n)。

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public int FindGreatestSumOfSubArray(int[] array)
	{
		ArrayList<Integer> list = new ArrayList<Integer>();
		int len = array.length;
		for(int i = 0;i<len;i++) {
			int sum = 0;
			for(int j = i;j<len;j++)
			{
				sum += array[j];
				list.add(sum);
			}

		}
       return Collections.max(list);
	}
}

二、动态规划法
假设$f(i)$f(i)表示以第$i$i个数字结尾的子数组的最大和，$max[f(i)],i=0,1,...,n-1$max[f(i)],i=0,1,...,n−1即为我们所要求的最大和。那么，$f(i) = \left\{ \begin{array}{l}a[i],i = 0orf(i - 1) \le 0,\\ f(i - 1) + a[i], i\ne0 and f(i - 1) > 0 \end{array} \right.$f(i)={a[i],i=0orf(i−1)≤0,f(i−1)+a[i],i̸​=0andf(i−1)>0​

public class Solution
{
	public  int FindGreatestSumOfSubArray(int[] array) {
		int result = array[0]; 
		int max=array[0];   
		for (int i = 1; i < array.length; i++) {
			max=Math.max(max+array[i], array[i]);
			result=Math.max(max, result);
		}
		return result;
	}
}