Answer to Question #204900 in C for Arunan Naicker

Question

Exercise 1: Largest contiguous partial sum

(a) Write a function that will find the largest contiguous partial sum, LagestSum, within an array of real numbers. That is,

we want to sum up any number of neighboring elements from the array, starting from anywhere, find the largest possible

sum.

-3 4 2 1 -4 6 -10 0 -4 3

then the function should report return 9, because 4+2+1+(-4)+6= 9 is the largest sum of contiguous elements from

that array of numbers. The function must also provide the starting and the ending indices of the summed elements back

to its caller(indices 1 and 5 for the example above).

(b) Write a driver program that tests the function LargesttSum written in (a)

Answer 1

#include<iostream>
#include<bits/stdc++.h>
using namespace std;


int largestSum(int arr[], int n)
{
	int maxsum = INT_MIN;
	int start=0;
	int sum =0;
	int end=0;
	int s=0;
	for(int i=0; i<n; i++)
	{
		sum += arr[i];
		if(sum > maxsum)
		{
			maxsum = sum;
			end = i;
			start = s;
		}
		
		if(sum<0)
		{
			sum =0;
			s = i + 1;
		}
	}
	
	cout<<endl;
	cout<<"Start index : "<<start<<endl<<"End index : "<<end;
	if(maxsum == INT_MIN)
	{
		return -1;
	}
	else
	{
		return maxsum;
	}
}


int main()
{
	cout<<"Enter array size : ";
	int n;
	cin>>n;
	
	int arr[n];
	cout<<"Enter array elements : ";
	for(int i=0; i<n; i++)
	{
		cin>>arr[i];
	}
	
	int ans = largestSum(arr, n);
	cout<<endl<<"Largest Contiguous sum of the given array elements is : ";
	cout<<ans<<endl;
	
}