c++ - 动态编程:计算一组中存在多少个升序子集

问题是：
给定一个整数n和一个由n个整数组成的数组v，计算用这些数字可以形成多少升序子集。
有一些限制：
1≤n≤300
v[i]≤1.000.000，无论1≤i≤n
s≤10^18
例如，下面是一个例子：

Input :
6
5 2 6 1 1 8

Output:
15

说明：有15个升序子集。
{5}，{2}，{6}，{1}，{1}，{8}，{5，6}，{5，8}，{2，6}，{2，8}，{6，8}，{1，8}，{1，8}，{5，6，8}，{2，6，8}。
我把这个问题当作作业来做。我已经搜索过堆栈溢出、数学堆栈等，但找不到任何想法。
如果你能给我一些关于如何解决这个问题的提示，那将是非常有帮助的。
编辑：
所以我想出了这个解决方案，但显然它在某个地方溢出了你能帮我吗

#include <iostream>
#include <fstream>
#include <queue>

using namespace std;
ifstream fin("nrsubsircresc.in");
ofstream fout("nrsubsircresc.out");

int v[301];
int n;
long long s;

queue <int> Coada;

int main()
{
    fin >> n;
    for(int i = 0; i < n; i++)
    {
        fin >> v[i]; // reading the array
        s++;
        Coada.push(i);
    }
    while(!Coada.empty()) // if the queue is not empty
    {
        for(int k = Coada.front() + 1; k < n; k++) //
            if( v[k] > v[Coada.front()] )
            {
                s++;
                Coada.push(k);
            }
        Coada.pop();
    }
    fout << s;
    return 0;
}

最佳答案

我在这里实现了贪婪的方法：

#include <algorithm>
#include <vector>
#include <array>

using namespace std;
using ll = long long;

const int N = 6;
array<int, N> numbers = { 5, 2, 6, 1, 1, 8 }; // provided data

vector<ll> seqends(N);
int main() {
    for (int i = 0; i < N; ++i) {
        // when we adding new number to subarray so far,
        // we add at least one ascending sequence, which consists of this number
        seqends[i] = 1;
        // next we iterate via all previous numbers and see if number is less than the last one,
        // we add number of sequences which end at this number to number of sequences which end at the last number
        for (int j = 0; j < i; ++j) {
            if (numbers[j] < numbers[i]) seqends[i] += seqends[j];
        }
    }

    // Finally we sum over all possible ends
    ll res = accumulate(seqends.cbegin(), seqends.cend(), (ll)0);
    cout << res;
}

该算法需要O（N）空间和O（N2）时间。