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

柿子饼同学

#include <bits/stdc++.h>
using namespace std;
int max(int, int);
int max(int a, int b){
        return a > b ? a : b;
}
int main(){
        int maxv = 0;
        vector<int> dp;
        vector<int> nums;
        int n;
        int k; 
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
                scanf("%d", &k);
                nums.push_back(k);
        }
        dp.push_back(nums[0]);
        for(int i = 0; i < n; ++i){
                dp[i] = max(dp[i-1] + nums[i], nums[i]);
                if(dp[i] > maxv){
                        maxv = dp[i];
                }
        }
        printf("%d", maxv);
        return 0;
}

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

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也是向量数组

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

#include <bits/stdc++.h>
using namespace std;
int max(int, int);
int max(int a, int b){
        return a > b ? a : b;
}
int main(){
        int maxv = 0;
        vector<int> dp(100);
        vector<int> nums(100);
        int n;
        int k; 
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
                scanf("%d", &k);
                nums.push_back(k);   //改过了 
        }
        dp.push_back(nums[0]);   //改过了 
        for(int i = 0; i < n; ++i){
                dp.push_back(max(dp[i-1] + nums[i], nums[i])); //改过了 
                if(dp[i] > maxv){
                        maxv = dp[i];
                }
        }
        printf("%d", maxv);
        return 0;
}

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

傻眼貓咪

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

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

柿子饼同学

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

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

傻眼貓咪

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

傻眼貓咪

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

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

#include <iostream>
#include <vector>
#include <algorithm>

int C(size_t i, size_t j, std::vector<int> X, std::vector<int> Y){
        if(!i || !j) return 0;
        else if(X[i] == Y[j]) return C(i-1, j-1, X, Y) + 1;
        return std::max(C(i, j-1, X, Y), C(i-1, j, X, Y));
}

int main() {
        int A[] = {1, 3, 4, 5, 6, 7, 7, 8};
        int B[] = {3, 5, 7, 4, 8, 6, 7, 8, 2};
        size_t m = (sizeof(A)/sizeof(int)); // A 长度
        size_t n = (sizeof(B)/sizeof(int)); // B 长度
        std::vector<int> X(A, A+m); // vector 赋值
        std::vector<int> Y(B, B+n); // vector 赋值
        std::cout << C(m, n, X, Y); // 答案：5
        return 0;
}

傻眼貓咪

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

中文版本：