最大连续子串

问题描述：

给定一个由数字组成的数组，求出和最大的子数组

求解方法：

1.暴力法

选取所有连续和的可能性，O(n^2)

2.分析法

当遍历到第i个元素时，判断在它前面的连续子序列和是否大于0，如果大于0，则以位置i结尾的最大连续子序列和为元素i和前门的连续子序列和相加；否则，则以位置i结尾的最大连续子序列和为元素i。

3.动态规划

记s[i]是以a[i]结尾的最大子数组和

s[i+1]=max(s[i]+a[i+1],a[i+1])

s[0]=a[0];

遍历数组a[i]即可得到以每一项结尾的最大子数组和s[i],求出其中最大值

package offer_0831; import java.util.Collections; import java.util.LinkedList; import java.util.List; public class MaxSerialSubList { // 暴力法 - func1 - 略 // 分析法 Integer func2(List<Integer> nums) { int maxRes = 0; int resBefore = 0; for (Integer i : nums) { if (resBefore < 0) { resBefore = i; } else { resBefore = i + resBefore; maxRes = maxRes > resBefore ? maxRes : resBefore; } } return maxRes; } // 动态规划 Integer func3(List<Integer> nums) { List<Integer> res = new LinkedList<Integer>(); res.add(nums.get(0)); for(int i = 1;i< nums.size();i++){ res.set(i,res.get(i-1)+nums.get(i)>0?res.get(i-1)+nums.get(i):nums.get(i)); } return Collections.max(res); } }