題目連結:
題目大意:
題目有多筆測試資料,每筆測試資料佔兩列。第一列給定一正整數 N (1 ≦ N ≦ 10 ^ 5),代表現在有 N 個相異正整數。第二列則是這 N 個數的值(介於 1 ~ 10 ^ 9 之間)
現在要從這 N 個數字中挑出一些數字(保持數字間原有的相對位置),使得挑出來的序列之最左邊以及最右邊的數字皆小於這兩者以外的數字(從最左邊第二個數到最右邊第二個數的所有數)。並使這個序列越長越好。
輸出序列最長之長度為何?
5
1 9 8 2 6
5
10 9 8 2 1
5
1 9 2 8 6
先將原有的 N 個數重新排列(但是要記錄原本的位置),例如:數列 1 、 9 、 8 、 2 、 6 重新由小到大排之後,現在依序的各自原有之位置, 1 、 4 、 5 、 3 、 2。
接著就照現在排序後的順序去由左往右掃過一次,並定義 L = N + 1 、 R = 0 、 C = 0 ,分別代表當前的左右端點以及包含於其中的數字。在每次掃到新數字的時候更新 L 、 R 兩端點的位置,然後求 R - L - C + 2 的值(這適用於 N > 1 的情況, N = 1 時額外判斷即可),最後將 C 加一。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。