In this program, we are going to find the maximum subarray sum using kadane algorithm. We will also use recursion and solve problems available on other platform..
Subarray: Continous part of an array. Maximum sub-array is defined in terms of the sum of the elements in the sub-array

Maximum Subarray Sum Kadane Algorithm

Naive approach would be to generate all the subarray and calculate the sum of each subarray and find the maximum one. In this case, its time complexity will be O(n^2).

Best approach to this problem in linear time complexity is to use kadane algorithm. In this algorithm, we include array element until it make the entire sum of the subarray not less than zero. If it does means at some point sum becomes less than zero then we exclude it and make sum equals to zero and continue;

Maximum Subarray Sum using Kadane Algorithm

In this program, we will take two variables, one for current sum and another will be maximum sum. We will initialize maximum sum with the lowest integer value which is INT_MIN. Then, iterate over the array and the array element in current sum. If current sum is less than the maximum sum then update maximum sum with the value of current sum.

If current sum is less than 0, then we can make current sum zero. Return the maximum sum.

int kadane(int *arr, int n)
{
	int curr_sum = 0;
	int mx = INT_MIN;
	for (int i = 0; i < n; i++)
	{
		curr_sum += arr[i];
		mx = max(mx, curr_sum);

		if (curr_sum < 0)
			curr_sum = 0;
	}
	return mx;
}

Maximum Subarray using Recursion

int maxSubArray(vector<int> &arr, int &ans, int i = 0)
{
	if (i == arr.size())
		return 0;
	int temp = maxSubArray(arr, ans, i + 1);
	int op1 = arr[i] + (temp > 0 ? temp : 0);
	ans = max(ans, op1);
	return op1;
}
int maxSubArray(vector<int> &arr)
{
	int ans = INT_MIN;
	maxSubArray(arr, ans, 0);
	return ans;
}

Maximum Subarray Sum Leetcode Solution

class Solution
{
public:
	int maxSubArray(vector<int> &arr)
	{
		int n = arr.size();
		int curr_sum = 0;
		int mx = INT_MIN;
		for (int i = 0; i < n; i++)
		{
			curr_sum += arr[i];
			mx = max(mx, curr_sum);

			if (curr_sum < 0)
				curr_sum = 0;
		}
		return mx;
	}
};

Maximum Sub Array GFG Solution

In this problem, we have to return the subarray having a maximum sum.

 

  1. Find the maximum sum using the kadane algorithm and store it in variable k.
  2. Find the longest subarray of sum k

In this problem, we need to print the subarray which has maximum sum.

vector<int> findSubarray(int arr[], int n)
{
	// code here

	long long int curr_sum = 0;
	long long int mx = INT_MIN;
	for (int i = 0; i < n; i++)
	{
		if (arr[i] < 0)
		{
			curr_sum = 0;
			continue;
		}

		curr_sum += arr[i];
		mx = max(mx, curr_sum);
	}
	long long int k = mx;
	// cout<<k<<endl;
	if (mx < 0)
	{
		return {-1};
	}
	vector<int> ans;
	long long int i = 0, j = 0;
	long long int mx2 = 0;
	long long int sum = 0;
	int startIndex = -1, endIndex = -1;
	while (i < n && j < n)
	{
		if (arr[j] < 0)
		{
			sum = 0;
			j++;
			i = j;
			continue;
		}

		sum += arr[j];
		if (sum < k)
		{
			j++;
		}
		else if (sum == k)
		{
			if (mx2 < j - i + 1)
			{
				startIndex = i;
				endIndex = j;
				mx = j - i + 1;
			}
			j++;
		}
	}
	// cout<<startIndex<<" "<<endIndex<<endl;

	for (int i = startIndex; i <= endIndex; i++)
	{
		ans.push_back(arr[i]);
	}

	return ans;
}
This is all about the Maximum Subarray Sum Kadane Algorithm. Thanks for reading this blog post. If you have any doubts regarding this problem, let me know in the comment section
Array