C++ Tutorials

C++ Tutorials

C++ program to program to find the sum of contiguous subarray: This tutorial better explains step by step the program for how to find the maximum sum of a sub-array in an Array in C++ with complete code and program output.

#include<bits/stdc++.h>
#include<iostream>

using namespace std;

int main(){

int n;
cout<<"Enter a number of element array: ";
cin>>n;
int arr[n];
int maximumSum=0;
int currentSum=0;
int left=-1;
int right=-1;
for(int i=0; i<n; i++){
  cout<<"Enter "<<i+1<<" element: ";
  cin>>arr[i];
}
//Generate all SubArray
//Element of SubArray(i,j)
for(int i=0; i<n; i++){
  for(int j=i; j<=n; j++){
    currentSum=0;

    for(int k=i; k<=j; k++){
      currentSum +=arr[k];
    
    }
    //update maximumSum if currentSum > maximumSum
    if(currentSum > maximumSum){
      maximumSum = currentSum;
      left = i;
      right = j;

    }
  }
}
//Print all maximumSum
cout<<"maximumSum is "<<maximumSum<<endl;
//Print the SubArray
for(int k = left; k<=right; k++){
  cout<<arr[k]<<",";
}
return 0 ;
}