Write an efficient C+ + program to find the sum of contiguous subarray within a vector of numbers which has the largest sum.

Function Definition

int maxSum (vector a)

The program to this question can be given as:

Program:

#include / /include header file.

#include

using namespace std;

int maxSum (vector a); / /function declaration

int maxSum (vector a) / /function definition

{

int i, n=a. size (), max_fast = 0, max_end = 0; / /declare variable

for (i = 0; i < n; i++) / /for loop

{

max_end = max_end + a[i]; / /add value in max_end

if (max_end < 0) / /check value

{

max_end = 0;

}

if (max_fast < max_end)

{

max_fast = max_end; / /assign value to max_fast

}

}

return max_fast; / /return value.

}

int main () / /main function.

{

vector a;

//insert values.

a. push_back (-2);

a. push_back (-3);

a. push_back (4);

a. push_back (-1);

a. push_back (-2);

a. push_back (1);

a. push_back (5);

a. push_back (-3);

int max_sum; / /define variable

max_sum = maxSum (a); / /calling function.

printf ("Maximum contiguous sum is %d/n", max_sum); / /print value.

return 0;

}

Output:

Maximum contiguous sum is: 7

Explanation:

In the above program firstly we include header files. the we declare the function that name is already given in the question. In that function we declare variable and assign a value to variable. Then we declare the loop that is used for add the value of max_end. In this loop we use the multiple if statements in first if block we check that the value of max_end less then 0. When the condition is true max_end = 0. In second if block we check that max_fast value is less then max_end. If it is true so we assign max_fast=max_end and return max_fast value. In the last we declare the main function. In this we assign the value in array and pass the array into the function and call the function. The ma_sum variable hold the return values of the function and in the last we print max_sum value.