动规初解||最大子序和 最长上升子序列53、128

53. 最大子序和

给定一个整数数组 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]

1. ans=-2 sum=0 ，ans=0
2. sum>0(n) sum=num=1 ans=1
3. sum>0(y) sum=-2 ans=1
4. sum>0(n) sum=num=4 ans=4
5. sum>0(y) sum=3 ans=4
6. sum>0(y) sum=5 ans=5
7. sum>0(y) sum=6 ans=6
8. sum>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;
    }
}

300. 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [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;
}
}