CDEC2203 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Meet the Multivengers - CDEC2203

Author: Harshit Chaudhary
Tester: Shreenath Asati
Editorialist: Harshit Chaudhary

DIFFICULTY:

EASY

PREREQUISITES:

Kadane’s Algorithm

PROBLEM:

You are given an array of powers of the superheroes and need to form a group in consecutive manner such that the sum of powers of that group is maximum of all the possible groups. You need to print that maximum sum.

EXPLANATION:

You simply need the maximum sum sub-array, which can be efficiently given by the Kadane’s Algorithm.

SOLUTIONS:

Setter's Solution 
	#include <iostream>
	using namespace std;
	long long int maxSubArraySum(int a[], int size);
	
	int main() {
		int t;
		cin >> t;
		while(t--){
		    int n;
		    cin >> n;
		    int powers[n];
		    for(int i=0; i<n; i++){
		        cin >> powers[i];
		    }

		    long long int ans;
		    ans = maxSubArraySum(powers, n);
		    cout << ans << endl;
		}
		return 0;
	}
	
	//code snippet taken from gfg
	long long int maxSubArraySum(int a[], int size)
	{
	    long long int max_so_far = a[0], max_ending_here = 0;
	 
	    for (int 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;
	}