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<cstdio>    //include header file.

#include<vector>

using namespace std;

int maxSum(vector <int>a);  //function declaration

int maxSum(vector <int>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<int> 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.