求一个序列里连续子序列的最大长度

柿子饼同学

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int max(int, int);
   
4. int max(int a, int b){
   
5.         return a > b ? a : b;
   
6. }
   
7. int main(){
   
8.         int maxv = 0;
   
9.         vector<int> dp;
   
10.         vector<int> nums;
    
11.         int n;
    
12.         int k;
    
13.         scanf("%d", &n);
    
14.         for(int i = 0; i < n; i++){
    
15.                 scanf("%d", &k);
    
16.                 nums.push_back(k);
    
17.         }
    
18.         dp.push_back(nums[0]);
    
19.         for(int i = 0; i < n; ++i){
    
20.                 dp[i] = max(dp[i-1] + nums[i], nums[i]);
    
21.                 if(dp[i] > maxv){
    
22.                         maxv = dp[i];
    
23.                 }
    
24.         }
    
25.         printf("%d", maxv);
    
26.         return 0;
    
27. }

复制代码

我的代码不知道为啥 , 不输出...
就是给一个整数的数组 , 要找其中一个有最大和的连续子数组 , 返回最大值
我看人动态规划视频写的 , 还是不太明白
求助 , 谢谢~

a327904410

输入没取地址，打个 & 试试

柿子饼同学

a327904410 发表于 2022-3-20 23:53
输入没取地址，打个 & 试试

谢谢提醒 , 但是还是没有输出

傻眼貓咪

我不知道你的代码是否正确，但我觉得你的问题出现在：
scanf() 里面忘记 &
vector 向量没有定义长度情况下，不能直接下标赋值，可以试试用 vector 里的 push_back() 如同 Python 里的 list.append() 一样。

柿子饼同学

傻眼貓咪 发表于 2022-3-21 08:12
我不知道你的代码是否正确，但我觉得你的问题出现在：
scanf() 里面忘记 &
vector 向量没有定义长度情况 ...

都改了 , 还是不行...

傻眼貓咪

柿子饼同学 发表于 2022-3-21 09:18
都改了 , 还是不行...

dp[0] = nums[0]; 也有改？
因为dp也是向量数组

柿子饼同学

傻眼貓咪 发表于 2022-3-21 10:54
dp[0] = nums[0]; 也有改？
因为dp也是向量数组

好了 , 现在打印的是一个奇怪的值

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int max(int, int);
   
4. int max(int a, int b){
   
5.         return a > b ? a : b;
   
6. }
   
7. int main(){
   
8.         int maxv = 0;
   
9.         vector<int> dp(100);
   
10.         vector<int> nums(100);
    
11.         int n;
    
12.         int k;
    
13.         scanf("%d", &n);
    
14.         for(int i = 0; i < n; i++){
    
15.                 scanf("%d", &k);
    
16.                 nums.push_back(k);   //改过了
    
17.         }
    
18.         dp.push_back(nums[0]);   //改过了
    
19.         for(int i = 0; i < n; ++i){
    
20.                 dp.push_back(max(dp[i-1] + nums[i], nums[i])); //改过了
    
21.                 if(dp[i] > maxv){
    
22.                         maxv = dp[i];
    
23.                 }
    
24.         }
    
25.         printf("%d", maxv);
    
26.         return 0;
    
27. }

复制代码

我设初始大小了结果打印一个 0

傻眼貓咪

柿子饼同学 发表于 2022-3-21 11:05
好了 , 现在打印的是一个奇怪的值

哈哈，可以打印表示代码没有问题，只是代码不对而已

柿子饼同学

傻眼貓咪 发表于 2022-3-21 11:09
哈哈，可以打印表示代码没有问题，只是代码不对而已

话说您是怎么学动态规划的呀
我感觉好难懂
这是不是就是一种递归啊

傻眼貓咪

我都是自学的，但只懂皮毛，称不上“会”
确实难懂
很多题目都是从递归演变而来的，比如：二叉树也可以用递归

傻眼貓咪

柿子饼同学 发表于 2022-3-21 11:14
话说您是怎么学动态规划的呀
我感觉好难懂
这是不是就是一种递归啊

我是用 LCS 公式写的代码，公式如图：
代码：

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. 
   
5. int C(size_t i, size_t j, std::vector<int> X, std::vector<int> Y){
   
6.         if(!i || !j) return 0;
   
7.         else if(X[i] == Y[j]) return C(i-1, j-1, X, Y) + 1;
   
8.         return std::max(C(i, j-1, X, Y), C(i-1, j, X, Y));
   
9. }
   
10. 
    
11. int main() {
    
12.         int A[] = {1, 3, 4, 5, 6, 7, 7, 8};
    
13.         int B[] = {3, 5, 7, 4, 8, 6, 7, 8, 2};
    
14.         size_t m = (sizeof(A)/sizeof(int)); // A 长度
    
15.         size_t n = (sizeof(B)/sizeof(int)); // B 长度
    
16.         std::vector<int> X(A, A+m); // vector 赋值
    
17.         std::vector<int> Y(B, B+n); // vector 赋值
    
18.         std::cout << C(m, n, X, Y); // 答案：5
    
19.         return 0;
    
20. }

复制代码

傻眼貓咪

柿子饼同学 发表于 2022-3-21 11:14
话说您是怎么学动态规划的呀
我感觉好难懂
这是不是就是一种递归啊

中文版本：