程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 最長單調遞增子序列問題

最長單調遞增子序列問題

編輯:關於C

最長單調遞增子序列問題

題目:設計一個 O( n ^ 2 )復雜度的算法,找出由 n 個數組成的序列的最長單調遞增子序列。


import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		while (scanner.hasNext()) {
			int n = scanner.nextInt();

			int[] nums = new int[n + 1];// 數列數據
			int[] sub_len = new int[n + 1];// sub_len[i]表示從i到n的最長遞增序列的長度
			int[] sub_index = new int[n + 1];// sub_index[i]表示第i個數據的後面一個數據的下標

			for (int i = 1; i <= n; i++) {
				nums[i] = scanner.nextInt();
				sub_len[i] = 1;
				sub_index[i] = 0;
			}

			for (int i = n - 1; i >= 1; i--) {
				int max = 0, p = 0;// 臨時變量
				for (int j = i + 1; j <= n; j++) {
					if (nums[i] < nums[j] && sub_len[j] > max) {
						max = sub_len[j];
						p = j;
					}

					if (p != 0) {
						sub_len[i] = sub_len[p] + 1;
						sub_index[i] = p;
					}
				}
			}

			int max = 0, p = 0;
			for (int i = 1; i <= n; i++) {
				if (sub_len[i] > max) {
					max = sub_len[i];
					p = i;
				}
			}
			System.out.println("最長長度:" + max);

			System.out.print("最長遞增序列:");
			while (p != 0) {
				System.out.print(nums[p] + " ");
				p = sub_index[p];
			}
			System.out.println();
		}
		scanner.close();
	}
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved