PREE03 - Editorial

Problem Link:

Contest

Difficulty:

Easy-Medium

Pre-Requisites:

Understanding of arrays

Problem:

Find the maximum sum of costs that Himesh can purchase from a list of shops by forming associations.

Explaination:

This is just a maximum subarray problem in which you have to find the largest possible continous sum of values inputted. This can be done as follows:


Keep two variables max_so_far and max_ending_here and initialise both with 0.

Now scan array from 1st element to last and for each element, add its value to max_ending_here which if becomes less than 0, then is reinitialised to 0 and if it becomes more than max_so_far replace the value of max_so_far with its value. Return the value of max_so_far in the end.

Now if all numbers entered are negative then largest number is the answer otherwise returned value.


Actual program for this is:

#include &ltiostream&gt
#include &ltcstdio&gt
#include &ltcstdlib&gt
#include &ltclimits&gt
#include &ltcfloat&gt
using namespace std;
long maxSubArraySum(int a[], int size)
{
long max_so_far = 0, max_ending_here = 0;
int i;
for(i = 0; i &lt size; i++)
{
max_ending_here = max_ending_here + a[i];
if(max_ending_here &lt 0)
max_ending_here = 0;
if(max_so_far &lt max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}

int main()
{ int n,t;
cin>>t;
while(t–)
{ int flag=0,max=INT_MIN;
cin>>n;
int a[n];
for(int i=0;i &lt n;i++)
{cin&gt&gta[i]; if(a[i]&gt0) flag=1; if(max&lta[i]) max=a[i];}

if(flag==1)
{long max_sum = maxSubArraySum(a, n);
printf("%ld\n", max_sum);
}
else
printf("%d\n", max);
} return 0;
}

//