删列造序 III

题目描述

给定由 n 个小写字母字符串组成的数组 strs ，其中每个字符串长度相等。

选取一个删除索引序列，对于 strs 中的每个字符串，删除对应每个索引处的字符。

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

假设，我们选择了一组删除索引 answer ，那么在执行删除操作之后，最终得到的数组的行中的 每个元素 都是按字典序排列的（即 (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 这三列后，最终得到的数组是 A = [“bc”, “az”]。
这两行是分别按字典序排列的（即，A[0][0] <= A[0][1] 且 A[1][0] <= A[1][1]）。
注意，A[0] > A[1] —— 数组 A 不一定是按字典序排列的。

4
解释：如果删除的列少于 4 列，则剩下的行都不会按字典序排列。

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

提示

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

思路

问题求的是将一些数删除最后让所有是都是非递减的，这个问题可以置换为求数组中的最长上升子序列有多长。最终问题的答案为长度减去最长上序列的长度。

代码实现

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 个整数 $1,2,\cdots A_1,A_2,\cdots A_N$ 。请你从中选出 K 个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 $10^9+9$的余数。

注意，如果 X<0，我们定义 X 除以 $10^9+9$ 的余数是负(−X)除以 $10^9+9$ 的余数。

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

输入描述

第一行包含两个整数N, K;

以下N 行每行一个整数$A_I$。

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

输出描述

输出一个整数，表示答案。

样例

样例输入

5 3
-100000
-10000
2
100000
10000

样例输出

999100009

思路

之前是想用动态规划，但在递推的过程中，是需要进行取模操作，这回影响到状态转移过程中的变化，所以本题不宜使用动态规划。直接排序即可。

代码实现

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();}
}