Maximum subsequence sum problem

本文最后更新于:July 21, 2020 pm

Three algorithms with different complexity for that problem

Recently i have read several chapters of 《introduction to algorithms》.After reading it,i think have a general overview on how to solve the maximum subsequence problem .So i realized it by template and i want to share three algorithms with different complexity with you.

O(N 2)

this algorithm simply traverse the sequence, it is stupid but easy to understand.I realize it by using the reference to the array.

template<typename T, size_t N>
T maxsub_slow(T(&seq)[N]){
	T maxsum = 0;
	for (size_t i = 0; i < N; i++)
	{
		T thissum = 0;// i means the head of the subsequence
		for (size_t j = i; j < N; j++) {
			thissum += seq[j];//j is meant to traverse the remain sequence
            if (thissum > maxsum) {
				maxsum = thissum;
			}
		}
	}
	return maxsum;
}

the logical of this algorithm is just use the loop to traverse it.Thus,it is inefficient

O(N lgN)

this algorithm adopt the idea of divide and conquer. It split the problem into three part.

  1. subsequence from begin to the middle
  2. subsequence from middle to the end
  3. subsequence contains and span the middle

For the first and the second one,we can use recursion to solve it and the base situation is the sequence with only one element.For the third one,we can simply loop from the middle to the left and then loop from the middle to the right.Finally,we add two part together and compare with 1 and 2 to get the answer. The recursive equation is T(n)=2T(n/2)+T(1)*n,you can use the tree or substitution method or mathematical induction to obtain the complexity is O(NlgN).The code is as followed,i changed the way to achieve it.

template<typename T>
// nlgn for big O notation
T maxsub_slow(const vector<T>& array, int begin, int end) {
	if (begin == end) {
		if (array[begin] >= 0)return array[begin];
		return 0;
	}
	int center = (begin + end) / 2;
	T left = maxsub_slow(array, begin, center);
	T right = maxsub_slow(array, center + 1, end);
	T leftbound = 0, leftmaxbound = 0;
	for (int i = center; i >= begin; i--) {
		leftbound += array[i];
		if (leftbound > leftmaxbound) {
			leftmaxbound = leftbound;
		}
	}
	T rightbound = 0, rightmaxbound = 0;
	for (int i = center + 1; i <= end; i++) {
		rightbound += array[i];
		if (rightbound > rightmaxbound) {
			rightmaxbound = rightbound;
		}
	}
	T final = leftmaxbound + rightmaxbound;
	auto ret = { left, right, final };
	return std::max(ret);
}
template<typename T>
T maxsub_slow(const vector<T>& array) {
	return maxsub_slow(array, 0, array.size() - 1);
}

O(N)

The third algorithm is the most clever one since its complexity is only O(N),i will first attach my code and then explain it.

template <typename T>
T maxsub_fast(const vector<T>& seq) {
	int thissum=0, maxsum = 0;
	for (size_t i = 0; i < seq.size(); i++)
	{
		thissum += seq[i];
		if (thissum > maxsum)
		{
			maxsum = thissum;
		}
		if (thissum < 0) {
			thissum = 0;
		}
	}
	return maxsum;
}

The core and critical idea of this algorithm is if (thissum < 0) {thissum = 0;}because it is impossible that the subsequence started with a negative number or ended with a negative number.Moreover,when it comes to a sequence with sum < 0 you can also ignore it.Suppose the array starts with i and ends with j and j is the first index that make the sum of the array become to 0,for any p in [i,j],sum([p,j]) is smaller than sum([i,j]),because sum[i,p] must be positive.
So when sum([i,j])<0 you can just let i jump to i+1,which dramatically optimize the algorithm.

test of the time cosume

the test code(use variadic template,i think it is a clever method)

#include<ctime>
#include<utility>
using std::clock;
using std::forward;
template<typename f,typename ...args>
double codetime(f funtion, args&&...arg) {
	double start = clock();
	funtion(forward<args>(arg)...);
	double end = clock();
	return (end - start) /CLOCKS_PER_SEC;
}

and i select several dataset to test the time consume

int main() {
    int a[100000];
    for (int i = 0; i < 100000; i++) {
        a[i] = rand();
    }
    vector<int>test(a, a + sizeof(a) / sizeof(int));
    cout << "the first one " << codetime(maxsub_slow0<int, 100000>, a) << "     " << maxsub_slow0(a) << endl;
    cout << "the second one " << codetime(maxsub_slow1<int>,test, 0, 99999)<<"    "<<maxsub_slow1(test,0,99999) << endl;
    cout << "the third one " << codetime(maxsub_fast<int>,test) <<"     "<<maxsub_fast(test)<<endl;
}

I open the O2 optimize,here comes the result.

the first one 4.92 1643186939
the second one 0.086 1643186939
the third one 0.005 1643186939

summary

I introduce several algorithms with different complexity and analyse it.Hope it could help you.


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!