CareerCup Find a subarray

Given an array of pairs of the form <a, b>. We have to find a sub-array such that the 1st element in the pairs are in increasing order and the sum of 2nd element of the pairs in the sub-array is maximum possible

--------------------------------------------------------------------------------------------------------

Do you know what does subarray means ? It‘s continuous! So DP is enough like this:

int max_ending_here, max_ending_so_far = 0;
int begin, end = 0;
int begin_temp = begin;

for(int i = 1; i< pairsArray.length; i++)
{
	if(pairsArray[i-1].first < pairsArray[i].first)
	{
		if(max_ending_here < 0)
		{
			max_ending_here = pairsArray[i].second;
			begin_temp = i;
		}
		else
		{
			max_ending_here += pairsArray[i].second;
		}

		if(max_ending_here >= max_ending_so_far)
		{
			max_ending_so_far = max_ending_here;
			begin = begin_temp;
			end = i;
		}
	}
	else
	{	
		max_ending_here = 0;
		begin_temp = i; 
	}
}

CareerCup Find a subarray

原文：http://blog.csdn.net/taoqick/article/details/19609513