BAF - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Books and Friends

Authors: Aman Shah and Preeti Yadav
Testers: Rishabh Rathi and Aditya Sharma

DIFFICULTY:

EASY

PREREQUISITES:

Max-subarray Sum

PROBLEM:

Given an array A consisting of positive and negative numbers. Your task is to find the maximum subarray sum and print accordingly.

EXPLANATION:

To find the maximum subarray sum, Kadane’s Algorithm is used here.

The basic idea is to find all contiguous segments of an array whose sum will give us the maximum value. Kadane’s algorithm scans the given array from left to right. In the i_{th} step, it computes the subarray with the largest sum ending at i starting for each subarray.

For example, let us consider this array: [-4, 2, -5, 1, 2, 3, 6, -5, 1]
For the given array the maximum subarray exists for [1, 2, 3, 6] and the maximum sum is 12.

Algorithm

Now we look at the algorithm to find the maximum sum subarray.

  1. We have two variables max_till_here and max_sum and initialize each variable with the first element of our array.

  2. The max_till_here will hold the maximum of all elements or the maximum sum of all elements whichever is greater for a subarray. The max_sum will be our result variable which will contain the maximum of all max_till_here values.

  3. So, we start iterating from index 1 or the second element of our array and keep doing the above steps. We keep adding the current array element if its sum with max_till_here is greater than the current element otherwise the max_till_here holds the value of the current element. We also update the max_sum variable with the maximum of max_sum and max_till here on each iteration.

SOLUTIONS:

Setter's Solution - CPP 
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MAX 100000

ll maxSubArraySum(ll a[], ll size) {
	ll max_so_far = a[0];
	ll curr_max = a[0];
	for (ll i = 1; i < size; i++) {
		curr_max = max(a[i], curr_max+a[i]);
		max_so_far = max(max_so_far, curr_max);
	}
	return max_so_far;
}

int main() {
	ll t,n,a[MAX];
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(ll i=0;i<n;i++)
			cin>>a[i];
		ll max_sum = maxSubArraySum(a, n);
		
		if(max_sum>0)
			cout<<"Can study - "<<max_sum<<endl;
		else
			cout<<"Cannot study - "<<max_sum<<endl;
	}
	return 0;
}
Tester's Solution - Python 
def maxSubArraySum(a, size):
	max_so_far = a[0]
	curr_max = a[0]
	
	for i in range(1, size):
		curr_max = max(a[i], curr_max + a[i])
		max_so_far = max(max_so_far, curr_max)
		
	return max_so_far

for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))

	ans = maxSubArraySum(a, n)

	if ans>0:
		print("Can study - " + str(ans))
	else:
		print("Cannot study - " + str(ans))

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. :smile: