【C/C++】最大连续子序列和/动态规划

思路主要是看了晴神的算法笔记，实现是自己重新用vector实现了一下，对付逗号隔开的输入

#include <iostream>

#include <string>

#include <cmath>

#include <vector>

#include <cstdio>

using namespace std;

int main()

{

//    持续输入，以逗号隔开，换行符结束

    vector<int> data;

    int tmp;

    while (cin >> tmp) {

        data.push_back(tmp);

        if (cin.get() == '\n') break;

    }

    for(vector<int>::iterator it = data.begin(); it != data.end(); it++)

    {

        cout << *it << endl;

    }

//    dp vector初始化

    vector<int> dp;

    dp.push_back(data[0]);

    int mx = dp[0];

    int cnt = data.end() - data.begin();

    cout << cnt << endl;

    for (int i = 1; i < cnt; i++)

    {

        dp.push_back(max(data[i], (dp[i-1] + data[i])));

        if (dp[i] > mx)

        {

            mx = dp[i];

        }

    }

    cout << mx;

}

巴特西

【C/C++】最大连续子序列和/动态规划

最新文章

热门文章