CARDG - Editorial

editorial
1

PROBLEM LINK:

Practice
Contest

Author: Abhay Tiwari

DIFFICULTY:

Easy

PREREQUISITES:

Basic array and loops, Kadane’s algorithm.

EXPLANATION:

In this problem you have to find the largest sum of contiguous subarray.

Cards are numbered from 1 to N having either positive or negative value,

you have to pick cards numbered contiguous.

Suppose starting from left with the smallest subarray of length one say(arr[0]),

every time we will update the subarray sum by adding the next adjacent element of

the array. If the new subarray sum is greater than zero then we will continue the

same process else we will start with a new subarray, also we will keep track of max

subarray sum in a max variable comparing each updated subarray sum.

SOLUTION:

Setter's Solution 
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--){
	    int n;cin>>n;
	    vector<int>arr;
	    for(int i = 0;i<n;i++){
	        int a;
	        cin>>a;
	        arr.push_back(a);
	    }
	    
	    int max = 0;
	    int temp_max = 0;
	    for(int i = 0;i<n;i++){
	        temp_max+=arr[i];
	        
	        if(temp_max<0){
	            temp_max = 0;
	        }
	        if(temp_max>max){
	            max = temp_max;
	        }
	    }
	        cout<<max<<endl;
	}
	return 0;
}