Algorithm Problem: Longest Non-Descending Sub Array or Logest Increasing Subarray, Dynamic programming

By | 2012 年 12 月 23 日

The ordinary dynamic programing gives our an algorithm of time complexity O(n2).
However, we could achieve the result by O(n * logn).
Inorder to do this, we need an array named min4length to hold the minimum value in array for the last number of the subarray in each length we could get. For example, given array {1,2,0}, the first run min4len = {1}, second {1,2}, third {0,2}.
At each step i from 0 to array.size() – 1, we find out the position l in min4length that satisfy that min4len[l] > array[i], and all the values before l is small than array[i], if exists. that is min4len[j] < array[i],j < l.
This step we could do in O(log n) time by binary search.
Then if the l is equal to min4len.size(), that indicated that we get to new length record, just push the value array[i] into min4len.
Else, update the min4len[l] = array[i], if min4len[l] > array[i]. And this step will NOT break the non-decreasing attribute of the array min4len, so we could do binary search again.
At last, the min4len.size() is the max length we could achieve.



If we need to output all the values in the final sub-array, it’s much harder, we have to keep track for each length of sub-array. see the code below in function:longestNonDecreasingSubArray()



Problem
Given an array with integers, find the longest non-descending sub-array of the given array.
For example:
Given: {1,2,3,-1,0,1,2,3,4,-1}
Should find out: {-1,0,1,2,3,4} of length 6.



Codes

<

pre>
//
// main.cpp
// LongestIncreasingSubarray
//
// Created by Qiu Xiangyu on 12-12-23.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

include

using namespace std;

void printArray(vector array) {
for (size_t i = 0; i < array.size(); ++i) {
if (i > 0) {
cout<<“,”;
}
cout<<array[i];
}
cout<<endl;
}

int lengthOfLongestNonDecreasingSubArray(vector &array) {
if (array.size() == 0) {
return 0;
}
vector min4Length;
for (int i = 0; i < array.size(); ++i) {
int l = 0,h = (int)min4Length.size() – 1;
while (l <= h) {
int mid = (l + h) / 2;
if (min4Length[mid] <= array[i]) {
l = mid + 1;
} else {
h = mid – 1;
}
}
if (l == min4Length.size()) {
min4Length.push_back(array[i]);
} else {
if (min4Length[l] > array[i]) {
min4Length[l] = array[i];
}
}
printArray(min4Length);
}

return (int)min4Length.size();

}

vector longestNonDecreasingSubArray(vector &array) {
vector ret;
if (array.size() == 0) {
return ret;
}
vector min4Length;
vector<vector > pathes;
for (int i = 0; i < array.size(); ++i) {
int l = 0,h = (int)min4Length.size() – 1;
while (l <= h) {
int mid = (l + h) / 2;
if (min4Length[mid] <= array[i]) {
l = mid + 1;
} else {
h = mid – 1;
}
}
cout<<“step “<<i<<“, value “<<array[i]<<“, position “<<l<<“, in min4len: “;
printArray(min4Length);
if (l == min4Length.size()) {
min4Length.push_back(array[i]);
vector path;
if (l > 0) {
vector &prePath = pathes[l – 1];
for (int k = 0; k < prePath.size(); ++k) {
path.push_back(prePath[k]);
}
}
path.push_back(i);
pathes.push_back(path);
cout<<“new length, min4len: “;
printArray(min4Length);
cout<<” path: “;
printArray(path);
} else {
if (min4Length[l] > array[i]) {
min4Length[l] = array[i];
if (l > 0) {
vector &prePath = pathes[l – 1];
for (int k = 0; k < prePath.size(); ++k) {
pathes[l][k] = prePath[k];
}
}
pathes[l].back() = i;
cout<<“path for “<<l<<” is:”;
printArray(pathes[l]);
}
cout<<“old for length: “< &lpath = pathes.back();
for (int i = 0; i < lpath.size(); ++i) {
ret.push_back(array[lpath[i]]);
}
return ret;
}

int main(int argc, const char * argv[])
{
vector arr = {1,2,3,-1,0,1,2,3,4,-1};
// int longest = lengthOfLongestNonDecreasingSubArray(arr);
// cout<<longest<<endl;
vector larr = longestNonDecreasingSubArray(arr);
printArray(larr);
cout<<“length : “<<larr.size()<<endl;
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注