一、求数组连续最大子序列和
// 最大连续子数组的成绩 还有求和 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; }
二、滑动窗口求解连续子数组【最大平均值】
思路：
1.先将最大的滑动窗口数给打满 最大窗口等于 k
2.将求和后的sum 向右移动一位求和，并删除左侧的以为数值
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; } }
