LARGEST SUM CONTIGUOUS SUBARRAY

Hi,guys this is one of my favourite problem.
During my campus placement 2 or 3 interviewer ask me this question.

So first thing what the problem is:
example :arr[]={-2,-3,4,-1,-2,1,5,-3};
we have to find the largest sum that is possible in contiguous subarray

Here largest sum is 7(and subarray is (4,-1,-2,1,5)).
All other combination of subarray has sum less than 7.

Here is the simple brute force approach:
Its time complexity is:o(n^2)
space complexity:o(1) 

#include<bits/stdc++.h>
using namespace std;
int main(){
 int n,i,j;//size of array
 cout << "Enter size of array\n";
 cin>> n;

 int arr[n];
 cout << "Enter elements of array\n";
 for(i=0;i<n;i++){
  cin >> arr[i];
 }

 int max_so_far=0;
 for(i=0;i<n;i++){
  int current_sum=0;
  for(j=i;j<n;j++){
   current_sum+=arr[j];
   if(max_so_far<current_sum){
   max_so_far=current_sum;
  }
  }
  
 }

 cout << "maximum sum is:" << max_so_far;
 return 0;
}

Hey this is the optimization of above problem;

algorithm: kadane algorithm

Time Complexity:o(n)
Space Complexity:o(1)

#include<bits/stdc++.h>
using namespace std;
int main(){
 int n,i,j;//size of array
 cout << "Enter size of array\n";
 cin>> n;

 int arr[n];
 cout << "Enter elements of array\n";
 for(i=0;i<n;i++){
  cin >> arr[i];
 }

 int max_so_far=0;
 int curr_sum=0;

 int count=0;
 for(i=0;i<n;i++){
  if(arr[i]>0){
   count++;
  }
 }

 if(count==0){
  //means all elements are negative in array
  //so ans is simply maximum of array

  max_so_far=arr[0];
  for(i=1;i<n;i++){
   if(max_so_far<arr[i]){
    max_so_far=arr[i];
   }
  }
  cout << "maximum sum is:" << max_so_far;


 }
 else{
  for(i=0;i<n;i++){
   curr_sum+=arr[i];

   if(curr_sum<0){
    curr_sum=0;
   }
   
   if(max_so_far<curr_sum){
    max_so_far=curr_sum;
   }


  }



  cout << "maximum sum is:" << max_so_far;

 }

 
 return 0;
}