刪列造序 III

題目描述

給定由 n 個小寫字母字符串組成的數(shù)組 strs ，其中每個字符串長度相等。

選取一個刪除索引序列，對于 strs 中的每個字符串，刪除對應(yīng)每個索引處的字符。

比如，有 strs = [“abcdef”,“uvwxyz”] ，刪除索引序列 {0, 2, 3} ，刪除后為 [“bef”, “vyz”] 。

假設(shè)，我們選擇了一組刪除索引 answer ，那么在執(zhí)行刪除操作之后，最終得到的數(shù)組的行中的 每個元素 都是按字典序排列的（即 (strs[0][0] <= strs[0][1] <= … <= strs[0][strs[0].length - 1]) 和 (strs[1][0] <= strs[1][1] <= … <= strs[1][strs[1].length - 1]) ，依此類推）。

請返回 answer.length 的最小可能值 。

樣例

樣例輸入

strs = [“babca”,“bbazb”]
strs = [“edcba”]
strs = [“ghi”,“def”,“abc”]

樣例輸出

3
解釋：
刪除 0、1 和 4 這三列后，最終得到的數(shù)組是 A = [“bc”, “az”]。
這兩行是分別按字典序排列的（即，A[0][0] <= A[0][1] 且 A[1][0] <= A[1][1]）。
注意，A[0] > A[1] —— 數(shù)組 A 不一定是按字典序排列的。

4
解釋：如果刪除的列少于 4 列，則剩下的行都不會按字典序排列。

0
解釋：所有行都已按字典序排列。

提示

• n == strs.length
• 1 <= n <= 100
• 1 <= strs[i].length <= 100
• strs[i] 由小寫英文字母組成

思路

問題求的是將一些數(shù)刪除最后讓所有是都是非遞減的，這個問題可以置換為求數(shù)組中的最長上升子序列有多長。最終問題的答案為長度減去最長上序列的長度。

代碼實現(xiàn)

class Solution {public int minDeletionSize(String[] strs) {int len = strs[0].length();int[] dp = new int[len];Arrays.fill(dp, 1);int ans = 1;for(int j = 1; j < len; j++){for(int i = j - 1; i >= 0; i--){boolean ok = true;for(String s : strs){if(s.charAt(j) < s.charAt(i)){ok = false;break;}}if(ok) dp[j] = Math.max(dp[j], dp[i] + 1); }ans = Math.max(ans, dp[j]);}return len - ans;}
}

乘積最大

題目描述

給定 N 個整數(shù) $1,2,?A_1,A_2,?A_N$ 。請你從中選出 K 個數(shù)，使其乘積最大。

請你求出最大的乘積，由于乘積可能超出整型范圍，你只需輸出乘積除以 $10^9+9$的余數(shù)。

注意，如果 X<0，我們定義 X 除以 $10^9+9$ 的余數(shù)是負(?X)除以 $10^9+9$ 的余數(shù)。

即：0 - ( ( 0 - x ) % $10^9$ + 9)

輸入描述

第一行包含兩個整數(shù)N, K;

以下N 行每行一個整數(shù)$A_I$。

其中，$1<=k<=N<=10^5,?10^5<=A_i<=10^5$

輸出描述

輸出一個整數(shù)，表示答案。

樣例

樣例輸入

5 3
-100000
-10000
2
100000
10000

樣例輸出

999100009

思路

之前是想用動態(tài)規(guī)劃，但在遞推的過程中，是需要進行取模操作，這回影響到狀態(tài)轉(zhuǎn)移過程中的變化，所以本題不宜使用動態(tài)規(guī)劃。直接排序即可。

代碼實現(xiàn)

import java.util.*;
// 1:無需package
// 2: 類名必須Main, 不可修改public class Main {static int MOD = (int)1e9 + 9;public static void main(String[] args) {Scanner sc = new Scanner(System.in);//在此輸入您的代碼...int n = sc.nextInt(), k = sc.nextInt();long[] arr = new long[n];for(int i = 0; i < n; i++) arr[i] = sc.nextInt();Arrays.sort(arr);long ans = 1;int flag = 1, l = 0, r = n-1;if(k % 2 > 0){k--;ans = arr[r--];if(ans < 0) flag = -1;}while(k > 0){long s1 = arr[l] * arr[l+1];long s2 = arr[r] * arr[r-1];if(s1 * flag > s2 * flag){ans = (s1 % MOD) * ans % MOD;l += 2;}else{ans = (s2 % MOD) * ans % MOD;r -= 2;}k -= 2;}System.out.println(ans);sc.close();}
}