PREE03 - Editorial

editorial
, ,
1

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;

}