max_multiple.cpp

求乘积最大的子序列乘积,采用动态规划方法求解

#include <iostream>
using namespace std;

double max_multiple(double A[],int size);


void main()
{
	double A[] = {2,-2,2,-2};
	int size = sizeof(A)/sizeof(A[0]);

	cout << "max_multiple = " << max_multiple(A,size) << endl;
}



double max_multiple(double A[],int size)
{
	int i;

	int best = 1,worst =1 ,bcurrent = 1,wcurrent = 1;
	int be_start = -1,be_end = -1,bc_start = 0,bc_end = 0 ,wc_start = 0,wc_end =0;
	for(i=0;i<size;i++)
	{
		int t;
		//bcurrent存放当前最大值，wcurrent存放当前最小值
		bcurrent =  bcurrent * A[i];
		wcurrent =  wcurrent * A[i];
		if(bcurrent<wcurrent)
		{
			t = bcurrent, bcurrent = wcurrent,wcurrent = t;
			//bc_start...bc_end存放bccurrent对应范围
			//wc_start...wc_end存放wcurrent对应范围
			t = bc_start ,bc_start = wc_start,wc_start = t;
		}
		bc_end = i;
		wc_end = i;
		if(bcurrent>best)
		{
			best = bcurrent;
			be_start = bc_start;
			be_end = bc_end;
		}
		if(bcurrent<1)
		{
			bcurrent = 1;
			bc_start = i+1;
		}
		if(wcurrent>1) 
		{
			wcurrent = 1;
			wc_start = i+1;
		}

	}
	cout << "be_start=" << be_start << ",be_end=" << be_end << endl;
	return best;
}