Found Objects

find | egrep '\.(c|cpp|java|sh)$'

Longest Non-Decreasing Subsequence

(LongestNonDecreasingSubsequence.h) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#ifndef LONGESTNONDECREASINGSUBSEQUENCE_H
#define LONGESTNONDECREASINGSUBSEQUENCE_H

#include<vector>

class Position {
  private:
    int number;
    int max_sub_sequence;
    Position *Parent;
    int index;
  public:
    void update_number(int temp) {number = temp;}
    void update_max(int temp) {max_sub_sequence = temp;}
    void update_parent(Position *temp) {Parent = temp;}
    void update_index(int temp) {index = temp;}
    int get_index() {return index;}
    Position * get_parent() { return Parent;}
    int get_max() {return max_sub_sequence;}
    int get_number() {return number;}
    Position(int temp_number);
    void display();
};

void getInput();
void computeMaxSub();
void displayResults();

std::vector<Position> sequence;

#endif
(LongestNonDecreasingSubsequence.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

/*
 *  Andrew Donley 
 *  Dynamic Programming Problem:
 *  Longest NonDecreasing Subsequence
 *  June 18th, 2013
 */

#include "LongestNonDecreasingSubsequence.h"
#include<iostream>
#include<string>
#include<sstream>

using namespace std;

int main() {
  getInput();
  computeMaxSub();
  displayResults();
  return 0;
}

Position::Position(int temp_number) {
  number = temp_number;
  max_sub_sequence = 1;
}

void Position::display() {
  cout << endl << "Number: " << number << ", Index: " << index << ", Max: " << max_sub_sequence;
  return;
}

/*
 *  Gets the sequence from user input
 */
void getInput() {

  string input;
  int val, index = 0;
  Position *temp;

  cout << endl;
  cout << "Longest Non-Decreasing Subsequence" << endl;
  cout << "==================================" << endl;
  cout << "Please enter a sequence of numbers deliniated by spaces." << endl;
  cout << "Press 'return' to submit the sequence." << endl;
  getline(cin, input);

  istringstream iss(input);

  // Store the items
  while(iss >> val) {
    temp = new Position(val);
    temp->update_index(index);
    sequence.push_back(*temp);
    index++;
    delete temp;
  }

  return;
}

/*
 *  Computes the longest subsquence
 */
void computeMaxSub() {

  int largest_sub = 0;
  Position * temp_parent = NULL;

  for(vector<Position>::iterator i = sequence.begin(); i != sequence.end(); ++i) {
    for(int j = 0; j < i->get_index(); j++) {
      if(i->get_number() >= sequence.at(j).get_number() && sequence.at(j).get_max() > largest_sub) {
        largest_sub = sequence.at(j).get_max();
        temp_parent = &sequence.at(j);
      }
    }
    // Update the largest increasing subsequence
    i->update_parent(temp_parent);
    i->update_max(largest_sub+1);
    // Reset the values
    largest_sub = 0;
    temp_parent = NULL;

  }
  return;
}

/* 
 *  Outputs the longest subsequence to stdout
 */
void displayResults() {
  int largest = 0;
  Position * temp_position;
  vector<Position> output;

  for(vector<Position>::iterator i = sequence.begin(); i != sequence.end(); i++) {
    if(i->get_max() > largest) {
      largest = i->get_max();
      temp_position = &*i;
    }
  }

  while(temp_position != NULL) {
    output.push_back(*temp_position);
    temp_position = temp_position->get_parent();
  }

  cout << endl << "The longest subsequence had length: " << output.front().get_max() << endl << endl;

  while(!output.empty()) {
    cout << output.back().get_number();
    if(output.size() > 1)
      cout << " -> ";
    else
      cout << endl << endl;

    output.pop_back();
  }

  return;
}