蓝桥学院2019算法题2.19

1 package recursion;
2
3 import java.util.Arrays;
4
5 /**
6 * &＃64;author zsh
7 * &＃64;company wlgzs
8 * &＃64;create 2019-02-18 15:35
9 * &＃64;Describe 题4·最长连续递增子序列&＃xff08;部分有序&＃xff09;
10 * (1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)
11 */
12 public class Main7 {
13
14 /**
15 *
16 * &＃64;param arr 待查找数组
17 * &＃64;return 最长的递增子序列
18 */
19 static int[] subsequence(int[] arr){
20 int[] sub &＃61; new int[arr.length];
21 int begin &＃61; 0;
22 int end &＃61; 0;
23 int count &＃61; 0;
24 for (int i &＃61; 1; i ) {
25 if (arr[i] > arr[end]){
26 end &＃43;&＃43;;
27 }else {
28 if ((end - begin) > count){
29 int l &＃61; end - begin;
30 sub &＃61; new int[l&＃43;1];
31 for (int j &＃61; 0; j <&＃61; l ; j&＃43;&＃43;) {
32 sub[j] &＃61; arr[begin];
33 begin &＃43;&＃43; ;
34 }
35 }
36 begin &＃61; i;
37 end &＃61; i;
38 }
39 if (i &＃61;&＃61; arr.length -1){
40 if ((end - begin) > count){
41 int l &＃61; end - begin;
42 sub &＃61; new int[l&＃43;1];
43 for (int j &＃61; 0; j <&＃61; l ; j&＃43;&＃43;) {
44 sub[j] &＃61; arr[begin];
45 begin &＃43;&＃43; ;
46 }
47 }
48 }
49 }
50 return sub;
51 }
52
53 public static void main(String[] args) {
54 int[] sub &＃61; new int[]{1,9,2,5,7,3,4,6,8,0,1,2,3,4,5,6,8};
55 System.out.println(Arrays.toString(subsequence(sub)));
56 }
57 }