给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例: 输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
题解： 1、贪心 ans为数组首元素，sum初始化为0，遍历nums，若sum>0保留，并更新（对子序列和有增益效果），若sum<=0（对子序列和无增益效果），舍弃并且令其为当前遍历到的nums[i]
ans=-2 sum=0 ，ans=0sum>0(n) sum=num=1 ans=1sum>0(y) sum=-2 ans=1sum>0(n) sum=num=4 ans=4sum>0(y) sum=3 ans=4sum>0(y) sum=5 ans=5sum>0(y) sum=6 ans=6sum>0(y) sum=1 ans=6 …2、动规 dp[i]表示nums中以nums[i]结尾的最大子序和 dp[i]=max(dp[i-1]+nums[i],nums[j]) dp[i]时当前数字要么是与之前的最大子序和的和 时间复杂度O（n），空间复杂度O（n） 优化方法：只与前一项有关所以将dp数组换为int保存前一个的信息，优化后时间复杂度为O（1）。
solution： 1、贪心
class Solution { public int maxSubArray(int[] nums) { int ans = nums[0]; int sum = 0; for(int num: nums) { if(sum > 0) { sum += num; } else { sum = num; } ans = Math.max(ans, sum); } return ans; } }给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。 说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
题解： 1、动规 dp[i]是以nums[i]这个数结尾的最长递增子序列的长度 dp[i]=Math.max(dp[i],dp[j]+1)
Array.fill(dp,1) //dp数组全部初始化为1！ 子序列：不要求连续子序列 sloution：
class Solution { public int longestConsecutive(int[] nums) { int[] dp=new int[nums.length]; Arrays.fill(dp,1); for(int i=0;i<nums.length;i++){ for(int j=0;j<i;j++){ if(nums[j]<nums[i]) dp[i]=Math.max(dp[i],dp[i]+1); } } int res=0; for(int i=0;i<dp.length;i++){ res=Math.max(res,dp[i]); } return res; } }