Maximum sum sub-array

kadanes_algorithm.cpp

#include <iostream>
#include <algorithm>
#include <climits>
#include <tuple>
using namespace std;
tuple<int, int, int> maxsumsubarray(int *arr, int size)
{
	int start = 0, end = size-1, max_sum=INT_MIN, sum = 0;
	for(int i = 0; i < size; ++i)
	{
		sum += arr[i];
		if(max_sum < sum)
		{
			max_sum=sum;
			end = i;
		}
		if(sum<=0)
		{
			sum = 0;
			start = i+1;
		}
	}
	if(max_sum==INT_MIN) return {0, -1, 0};
	return {start, end, max_sum};
}
int main()
{
	int arr[] = {-1, 2, 0, 3, -4};
	int size = sizeof(arr)/sizeof(int);
	auto max_sum = maxsumsubarray(arr, size);
	for(int i = get<0>(max_sum); i <= get<1>(max_sum); ++i)
	{
		cout << arr[i] << ' ';
	}
	cout << '\n';
	cout << get<2>(max_sum) << '\n';
	return 0;
}