最大连续子串

问题描述给定一个由数字组成的数组求出和最大的子数组求解方法1.暴力法选取所有连续和的可能性O(n^2)2.分析法当遍历到第i个元素时判断在它前面的连续子序列和是否大于0如果大于0则以位置i结尾的最大连续子序列和为元素i和前门的连续子序列和相加否则则以位置i结尾的最大连续子序列和为元素i。3.动态规划记s[i]是以a[i]结尾的最大子数组和s[i1]max(s[i]a[i1],a[i1])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(ListInteger 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(ListInteger nums) { ListInteger res new LinkedListInteger(); 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); } }