|
发表于 2021-2-25 18:57:40
|
显示全部楼层
本楼为最佳答案
那就看标准答案吧
https://www.nowcoder.com/questio ... 1599b64dbdb8cdea3bd
- #include <stdio.h>
- #include <stdint.h>
- #define N 1010
- int arr[N];
- int dp[N]; // 最长递增子序列
- int max(int a, int b)
- {
- return a > b ? a : b;
- }
- int main()
- {
- //freopen("data.txt", "r", stdin);
- int n;
- while (scanf("%d", &n) != EOF)
- {
- for (int i = 0; i < n; i++)
- {
- scanf("%d", &arr[i]);
- }
- int maxVal = 0;
- for (int i = 0; i < n; i++)
- {
- dp[i] = arr[i];
- for (int j = 0; j < i; j++)
- {
- if (arr[i] > arr[j])
- { // 满足递增的子序列, 记录下 dp[i] 是子序列的和
- dp[i] = max(dp[i], dp[j] + arr[i]);
- if (dp[i] > maxVal)
- {
- maxVal = dp[i];
- }
- }
- }
- }
- printf("%d\n", maxVal);
- }
- return 0;
- }
复制代码
- input:
- 7
- 1 7 3 5 9 4 8
- iuput:
- 18
复制代码
这是执行完成后,两个数组中的内容
- 1: arr = {1, 7, 3, 5, 9, 4, 8, 0 <repeats 1003 times>}
- 2: dp = {1, 8, 4, 9, 18, 8, 17, 0 <repeats 1003 times>}
复制代码
如果看不懂代码,你可以调试一下,看看每一步后,dp数组的变化
|
|