Maximum Contigous subsequence Sum Problem

Given (Possible Negative) integers A1,A2,A3,..An, Find and identify the sequence corresponding too, The maximum value of sub-sequence is defined as sum of K in Input array from I to J

Obvious O(n3) Solution

#include <vector>
#include <iostream>

int maximum_subsequence_sum( std::vector<int> &input, int& start_pos, int& end_pos ) {
	int size    = input.size();
	int max_sum = 0;
	for ( int i = 0; i < size; i++) {
		for ( int j = i; j < size; j++) {
			int current_sum = 0;
			for ( int k = i; k <= j; k++) {
				current_sum += input[k];
			}
			if ( current_sum > max_sum ) {
				max_sum = current_sum;
				start_pos = i;
				end_pos   = j;
			}
		}
	}
	return max_sum;
}
int main ( int argc, char **argv) {
	int input1[6] = {-2, 11, -4, 13, -5, 2};
	std::vector<int> in1(input1, input1 + 6);
	int start_pos = 0;
	int end_pos   = 0;
	std::cout << "Sum = " << maximum_subsequence_sum(in1, start_pos, end_pos) << std::endl;
	for ( int i = start_pos; i <= end_pos; i++) {
		std::cout << in1[i] << " ";
	}
	std::cout << std::endl;
}

A quadratic maximum contiguous subsequence sum algorithm

#include <vector>
#include <iostream>

int maximum_subsequence_sum( std::vector<int> &input, int& start_pos, int& end_pos ) {
	int size    = input.size();
	int max_sum = 0;
	for ( int i = 0; i < size; i++) {
		int current_sum = 0;
		for ( int j = i; j < size; j++) {
			current_sum += input[j];
			if ( current_sum > max_sum ) {
				max_sum = current_sum;
				start_pos = i;
				end_pos   = j;
			}
		}
	}
	return max_sum;
}
int main ( int argc, char **argv) {
	int input1[6] = {-2, 11, -4, 13, -5, 2};
	std::vector<int> in1(input1, input1 + 6);
	int start_pos = 0;
	int end_pos   = 0;
	std::cout << "Sum = " << maximum_subsequence_sum(in1, start_pos, end_pos) << std::endl;
	for ( int i = start_pos; i <= end_pos; i++) {
		std::cout << in1[i] << " ";
	}
	std::cout << std::endl;
}

A linear maximum contiguous subsequence sum algorithm

#include <vector>
#include <iostream>

int maximum_subsequence_sum( std::vector<int> &input, int& start_pos, int& end_pos ) {
	int size    = input.size();
	int max_sum = 0;
	int current_sum = 0;

	for ( int i = 0, j = 0 ; j < size; j++) {		
		current_sum += input[j];
		if ( current_sum > max_sum ) {
			max_sum = current_sum;
			start_pos = i;
			end_pos   = j;
		} else if ( current_sum < 0 ) {
			i = j + 1;
			current_sum = 0;
		}
	}
	return max_sum;
}
int main ( int argc, char **argv) {
	//int input1[6] = {-2, 11, -4, 13, -5, 2};
	int input1[6] = {1,2,3,4,5,6};
	std::vector<int> in1(input1, input1 + 6);
	int start_pos = 0;
	int end_pos   = 0;
	std::cout << "Sum = " << maximum_subsequence_sum(in1, start_pos, end_pos) << std::endl;
	for ( int i = start_pos; i <= end_pos; i++) {
		std::cout << in1[i] << " ";
	}
	std::cout << std::endl;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s