最长递增子串 （只能忽略m个元素）

记录一道碰到的笔试题。

题目

给定一个int数组，求其最长的连续递增子序列，但递增过程中可以忽略m个数组元素。在最优子序列长度相同时，以子序列元素之和较小的一个为最优解*。
即实现方法

vector<int> getLongestSubAry(const vector<int>& array, int m)

思路

八成是动态规划，参考最长连续子序列。
需要存储状态：第i个元素的{最优序列，忽略元素个数}
从i向前寻找m个位置的最优解（因为最多只能忽略m个）。假设那个“之前的”元素是array[j]，那如果array[i]>array[j]并且array[j]+1>=当前最优序列长度，则判断限制条件*以确定是否更新最优解。
整个方法的复杂度应该是[latex]O(n*m)[/latex]，其中n为array的长度。

代码

#include <iostream>
#include <vector>
using namespace std;
struct OptmElem{
    vector<int> results;
    int omitCount;
    int getResultCount(){
        return results.size();
    }
};
int getSum(const vector<int>& ary){
    int sum = 0;
    for(int i=0; i<ary.size(); i++)
        sum += ary[i];
    return sum;
}
/**
* Find the longest increasing subarray
* that allows skipping m elements
*/
vector<int> maxSubArray(const vector<int>& array, int m){
    if(array.empty())
        return vector<int>();
    vector<OptmElem> bestResults;
    OptmElem initOptm;
    initOptm.results.push_back(array[0]);
    initOptm.omitCount = m;
    bestResults.push_back(initOptm);
    unsigned long maxLen = 0;
    int optiIndex = 0; //index of optimal result in bestResults
    for(int i=1; i<array.size(); i++){
        vector<int> currBest = {array[i]};
        int omitCount = m;
        for(int j=(i-m>=0)?(i-m):(0); j<i; j++){
            //trace back j steps
            //if omittance limit exceed, continue
            if(bestResults[j].omitCount < (i-j-1)){
                continue;
            }
            if((array[i] > array[j]) && (bestResults[j].getResultCount()+1 >= currBest.size())){
                //new optimal
                if(bestResults[j].getResultCount()+1  == currBest.size()){
                    //on-par result, array that has the smallest sum is the best
                    int oldSum = getSum(currBest);
                    int newSum = getSum(bestResults[j].results) + array[i];
                    if(newSum > oldSum){
                        continue; //omit this best
                    }
                }
                currBest = bestResults[j].results;
                currBest.push_back(array[i]);
                omitCount = bestResults[j].omitCount - (i-j-1);
            }
        }
        OptmElem elem;
        elem.results = currBest;
        elem.omitCount = omitCount;
        bestResults.push_back(elem);
        if(maxLen < currBest.size()){
            maxLen = currBest.size();
            optiIndex = i;
        } else if (maxLen == currBest.size()){
            int oldBestSum = getSum(bestResults[optiIndex].results);
            int currBestSum = getSum(currBest);
            if(currBestSum < oldBestSum){
                optiIndex = i;
            }
        }
    }
    return bestResults[optiIndex].results;
}