COINGME EDITORIAL

editorial
, , , ,
1

PROBLEM LINK
Alice And The Coin Game

Editorialist:-Faiz Alam
Author and Tester:-Prasoon Jain

PREREQUISITES
Kadane’s Algorithm

PROBLEM
Initially,Alice has 0 rupee she visited a fair in which shops have positive and negative coins.Positive indicate Alice will receive A[i] coin there ,negative indicates that she has to deposits A[i] coins there ,restriction being that Alice can only move across contiguous shops.Find the maximum number of coins she would have after visiting fair.

EXPLANATION
The statement Contiguous suggests that the question is simple implementation of Kadane’s Algorithm.Move only contiguous elements of array maintaining the previous contiguous elements sum,if adding the i’th shop coins results in increasing of the previous sum include those coins ,or if adding the i’th shop coins results in decreasing of the previous sum ,skip those elements .
If all the shops of fairs have negative coins simply skip all shops of the fair and return 0.

SOLUTIONS

Setter's Solution 
  package codeHeat;
  import java.util.Scanner;
  public class COINGME {
   public static void main(String[] args) {
	
	Scanner sc=new Scanner(System.in);
	int t=sc.nextInt();
	while(t>0) {
		int n=sc.nextInt();
		int arr[]=new int[n];
		for(int i=0;i<n;i++) {
			arr[i]=sc.nextInt();
		}
		
		
		int currSum=0;
		int maxTillNow=0;
		for(int i=0;i<n;i++) {
			currSum=currSum+arr[i];
			if(currSum>maxTillNow) {
				maxTillNow=currSum;
			}
			if(currSum<0) {
				currSum=0;
			}
		}
		if(maxTillNow<0)
			System.out.println(0);
		else
			System.out.println(maxTillNow);
		
		t--;
	}
}   }
Editorialist's Solution 
 #include<bits/stdc++.h>
 #define ll long long int
 using namespace std;
   ll maxSubArraySum(ll a[], ll size) 
  { 
   ll max_so_far = INT_MIN, max_ending_here = 0; 

  for (ll i = 0; i < size; i++) 
{ 
    max_ending_here = max_ending_here + a[i]; 
    if (max_so_far < max_ending_here) 
       {
              max_so_far = max_ending_here; 
       }
     

    if (max_ending_here < 0)
    {
        max_ending_here = 0; 
    }
        
} 
return max_so_far;  }


 int main()
    {

    ll t;
   cin>>t;
   while(t--)
  {

    int n;
    cin>>n;
    ll A[n];

    for(ll i=0;i<n;i++)
  {
      cin>>A[i];
  }
 
  ll count=0;
 for(ll i=0;i<n;i++)
 {
     if(A[i]<0)
     {
         count++;
     }
 }
 if(count==n)//Handling case when all the shops arevthe one where coins are deposited
 {
     cout<<0<<"\n";
 }
 else // Shops of the contiguous of both types
 {
     ll maxsum=maxSubArraySum(A, n);
    cout<<maxsum<<"\n";

 }

}
return 0;  }

Complexity:-O(N)

1 Like