今天就跟大家聊聊有關(guān)使用Java怎么計(jì)算數(shù)組中最長(zhǎng)的子序列，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來(lái)自于我們對(duì)這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過(guò)有效、簡(jiǎn)單的方式提供給客戶，將通過(guò)不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名申請(qǐng)、虛擬主機(jī)、營(yíng)銷軟件、網(wǎng)站建設(shè)、上林網(wǎng)站維護(hù)、網(wǎng)站推廣。

問(wèn)題：給定一個(gè)長(zhǎng)度為N的數(shù)組，找出一個(gè)最長(zhǎng)的單調(diào)自增子序列（不一定連續(xù)，但是順序不能亂） 例如：給定一個(gè)長(zhǎng)度為8的數(shù)組A{1，3，5，2，4，6，7，8}，則其最長(zhǎng)的單調(diào)遞增子序列為{1，2，4，6，7，8}，長(zhǎng)度為6。

思路1：第一眼看到題目，很多人肯定第一時(shí)間想到的是LCS。先給數(shù)組排個(gè)序形成新數(shù)組，然后再把新數(shù)組和原數(shù)組拿來(lái)求LCS，即可得到答案。這種解法很多人能想得到，所以就不再贅述。

思路2：按照思路1的想法，最后求LCS時(shí)還是得用到DP，我們干嘛不直接用DP來(lái)求解呢。對(duì)于數(shù)組arr，我們從后往前遍歷數(shù)組，分別求出當(dāng)子序列以arr[i]結(jié)尾時(shí)的最長(zhǎng)子序列，然后取其中的大值。即可得到整個(gè)數(shù)組的最長(zhǎng)子序列。 那么怎么求以arr[i]結(jié)尾時(shí)的最長(zhǎng)子序列呢，這就轉(zhuǎn)換成一個(gè)DP問(wèn)題了。要求arr[i]的最長(zhǎng)子序列，只需要求出arr[i-1]的最長(zhǎng)子序列。即：max{arr[i]}=max{arr[i-1]}+1。

java實(shí)現(xiàn)代碼：

public class arrDemo {
 public static void main(String[] args) {
  // int[] arr = {89, 256, 78, 1, 46, 78, 8};
  int[] arr = { 1, 3, 5, 2, 4, 6, 7, 8 };
  // int[] arr = {6, 4, 8, 2, 17};
  int max = 0;
  int maxLen = arr.length;
  // 從后往前遍歷數(shù)組，分別求出以arr[i]結(jié)尾的時(shí)候的最長(zhǎng)子序列長(zhǎng)度
  for (int i = arr.length - 1; i > 0; i--) {
   int[] newArr = new int[i];
   System.arraycopy(arr, 0, newArr, 0, i);
   int currentLength = 1 + dp(newArr, arr[i]);
   if (currentLength > max)
    max = currentLength;
   // 最長(zhǎng)子序列的長(zhǎng)度最長(zhǎng)為原始數(shù)組的長(zhǎng)度，
   // 因?yàn)椴恍枰覀兦笞铋L(zhǎng)子序列的元素，所以直接結(jié)束循環(huán)，減少時(shí)間開銷
   if (max == maxLen)
    break;
  }
  System.out.println(max);
 }
 public static int dp(int[] arr, int end) {
  // 遞歸結(jié)束條件
  if (arr.length == 1) {
   // 小于end則包含在子序列中，子序列長(zhǎng)度+1
   if (arr[0] <= end)
    return 1;
   else
    return 0;
  }
  // 遍歷數(shù)組，找到最靠近end的并且<=end的元素位置i
  for (int i = arr.length - 1; i >= 0; i--) {
   if (arr[i] <= end) {
    // 從i處截?cái)鄶?shù)組，將arr[0]到arr[i-1]組成新數(shù)組繼續(xù)遞歸求長(zhǎng)度
    int[] newArr = new int[i];
    System.arraycopy(arr, 0, newArr, 0, i);
    // 分別計(jì)算包含arr[i]時(shí)的最長(zhǎng)子序列和不包含arr[i]時(shí)的最長(zhǎng)子序列，取大值
    int containLen = dp(newArr, arr[i]) + 1;
    int notContainLen = dp(newArr, end);
    return containLen > notContainLen ? containLen : notContainLen;
   }
  }
  // 如果沒(méi)找到比end更小的，返回長(zhǎng)度為0
  return 0;
 }
}

運(yùn)行結(jié)果：

6

看完上述內(nèi)容，你們對(duì)使用Java怎么計(jì)算數(shù)組中最長(zhǎng)的子序列有進(jìn)一步的了解嗎？如果還想了解更多知識(shí)或者相關(guān)內(nèi)容，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝大家的支持。

分享名稱：使用Java怎么計(jì)算數(shù)組中最長(zhǎng)的子序列-創(chuàng)新互聯(lián)
網(wǎng)站地址：http://jinyejixie.com/article18/ddeidp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計(jì)、網(wǎng)站營(yíng)銷、微信公眾號(hào)、商城網(wǎng)站、自適應(yīng)網(wǎng)站、網(wǎng)站改版

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)