數組連續最大序列問題----【滑動視窗、動态規劃求解】

一、求數組連續最大子序列和

// 最大連續子數組的成績 還有求和
    public static int maxSubArray(int[] nums) {
        int res = nums[0];
        int sum = 0;
        for (int num : nums) {
            if (sum > 0)
                sum += num;
            else
                sum = num;
            res = Math.max(res, sum);
        }
        return res;
    }      

二、滑動視窗求解連續子數組【最大平均值】

public static double findMaxAverage(int[] nums, int k) {
  double ans = 0, sum = 0;
  for(int i = 0; i < k ; i++){
    sum = sum + nums[i];
  }
  ans = sum / k;
  
  for(int i = k; i< nums.length;i++){
    sum = sum + num[k] - nums[i-k];
    ans = Math.max(ans,sum/k);
  }
  return ans;
}      

三、數組最大非連續遞增子序列

public int ziXuLIE(int[] nums){
  if(num.length == 0) return 0;
  
  int[] dp = new int[nums.length];
  dp[0] = 1;
  int res = 1;
  
  for(int i =0; i < nums.length; i++){
    dp[i] = 1;
    for(int j = 0; j < i; j++){
      if(nums[i]>nums[j]){
        dp[i] = Math.max(dp[i], dp[j]+1);
      }
    }
    res = Math.max(res, dp[i]);
  }
  return res;
}      

五、連續最大遞增子序列的個數

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int ans = 0;
        int n = nums.length;
        int start = 0;
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] <= nums[i - 1]) {
                start = i;
            }
            ans = Math.max(ans, i - start + 1);
        }
        return ans;

    }
}      

六、最長連續遞增子序列

import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一維數組 the array
     * @return int整型一維數組
     */
    public int[] LIS (int[] arr) {
        // write code here
        int len = 1, n = arr.length;
        if (n == 0) {
            return new int[0];
        }
        int[] d = new int[n + 1];
        int[] w=new int[n];
        d[len] = arr[0];
        w[0] = len;
        for (int i = 1; i < n; ++i) {
            if (arr[i] > d[len]) {
                d[++len] = arr[i];
                w[i]=len;
            } else {
                int l = 1, r = len, pos = 0;
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < arr[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                 d[pos + 1] = arr[i];
                 w[i]=pos+1;
            }
        }
        int[] res=new int[len];
        for(int i=n-1,j=len;j>0;--i){
            if(w[i]==j){
                res[--j]=arr[i];
            }
        }
        return res;
    }
}