CDOUT1 - Editorial

editorial
,
1

PROBLEM LINK

Practice

Contest

Author: Md Majid Jahangir

Tester : Md Majid Jahangir

Editorialist: Md Majid Jahangir

DIFFICULTY:

Simple

PREREQUISITES:

Basics,Implementation

PROBLEM

Rohan has decided to trade in Gold. But as he is just starting out, he can only buy one unit of gold and then sell it at a later date. This is unfair for Rohan. To make up for this restriction, Rohan is given the price of gold of N days into the future from today. Can you help Rohan maximize his profit?

EXPLANATION

This is a Maximum Sub-Array problem. You need to generate an array which stores the change in price of gold from the previous day and find it's sub-array which has the maximum sum.

For example-
Price- 10 11 7 10 13 6
Change- 1 -4 3 3 -7

The maximum profit in this case is 6, which can be achieved if we buy on the 3rd day and sell the next day.

The above algorithm can be achieved by simple Brute Force method with time complexity O(n^2), but considering the constraints and time limit, this approach would give a TLE.

So, we use Divide-and-Conquer algorithm which will have a time complexity of O(nlog(n)).

We divide the array into two parts. We can find the maximum sub-array of Change[low…mid] and Change[mid+1…high] recursively, because these two sub-problems are smaller instances of the problem of finding maximum sub-array. Then we have to find the maximum sub-array that crosses
the midpoint, and then return the sub-array sum which the largest among the three.

The algorithm is described below-

Max_Sub_Array(Change,low,high)
	if(high==low)
		return(Change[low]);		//Base Case:Only one element
	else
		mid=(low+high)/2;
		left=Max_Sub_Array(Change,low,mid);	//Maximum sum of the left of the array
		right=Max_Sub_Array(Change,mid+1,high);  //Maximum sum of the right of the array
		cross=Max_Cross_Array(Change,low,mid,high);//Maximum sum of the whole array
		return max(left,right,cross);
Max_Cross_Array(Change,low,mid,high)
	left_sum=-INFINITY;
	sum=0;
	for i =mid to low
		sum+=Change[i];
		if(sum>left_sum)
			left_sum=sum;
	right_sum=-INFINITY;
	sum=0
	for j=mid+1 to high
		sum+=Change[i];
		if(sum>right_sum)
			right_sum=sum;
	return (left_sum+right_sum)

C++ Code:

#include<iostream>
#include<cstdio>
#include<ctime>

using namespace std;

long long int max_subarr(int[],long long int,long long int);
long long int cross_max_subarr(int[],long long int,long long int,long long int);
void solution();

int arr[100000];
int change[100000];

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		solution();
	}
	return 0;
}
void solution()
{
	long long int sum;
	long long int n,i;
	scanf("%lld",&n);
	for(i=0 ; i<n ; i++)
		scanf("%d",&arr[i]);
	for(i=0 ; i<n ; i++)
		change[i]=arr[i+1]-arr[i];
	sum=max_subarr(change,0,n-2);
	printf("%lld\n",sum);
}

long long int max_subarr(int arr[],long long int low,long long int high)
{
	long long int mid,left_sum,right_sum,cross_sum;
	if(high==low)
		return arr[low];
	else
	{
		mid=(low+high)/2;
		left_sum=max_subarr(arr,low,mid);
		right_sum=max_subarr(arr,mid+1,high);
		cross_sum=cross_max_subarr(arr,low,mid,high);
		if(left_sum>right_sum && left_sum>cross_sum)
			return left_sum;
		else if(right_sum>left_sum && right_sum>cross_sum)
			return right_sum;
		else
			return cross_sum;
	}
}

long long int cross_max_subarr(int arr[],long long int low,long long int mid, long long int high)
{
	long long int left_sum=-999999,sum=0,i=mid;
	while(i>=mid)
	{
		sum+=arr[i];
		if(sum>left_sum)
			left_sum=sum;
		i--;
	}
	sum=0;
	long long int right_sum=-999999;
	i=mid+1;
	while(i<=high)
	{
		sum+=arr[i];
		if(sum>right_sum)
			right_sum=sum;
		i++;
	}
	return (left_sum+right_sum);
}