Kadane's Algorithm

// Leetcode 53. Maximum Subarray,
//Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.A subarray is a contiguous part of an array.

/*APPROACH-
To print the subarray with the maximum sum the idea is to maintain start index of currSum at current index so that whenever maxSum is updated with currSum then start index and end index of subarray can be updated with start and current index.
EXAMPLE 1-
Input: [-3, -4, 5, -1, 2, -4, 6, -1]
Output: 8
Explanation: Subarray [5, -1, 2, -4, 6] is the max sum contiguous subarray with sum 8.
EXAMPLE 2-
Input: nums = [-2, 1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4 ,-1,2,1] has the largest sum = 6.
EXAMPLE 3-
Input: nums = [-2 , 3 , -1 , 2 , -2]
Output: 4
Explanation: [3, -1, 2] has the largest sum = 4*/

/*Complexity
• It is a very efficient algorithm as it uses
Time Complexity: O(n)
Auxiliary Space: O(1)*/

#include <algorithm>
#include <iostream>
#include <vector>
#include <climits>

using namespace std;
int maximumSubarraySum(vector < int > arr) {
  int n = arr.size();
  int maxSum = INT_MIN;

  for (int i = 0; i <= n - 1; i++) {
    int currSum = 0;
    for (int j = i; j <= n - 1; j++) {
      currSum += arr[j];
      if (currSum > maxSum) {
        maxSum = currSum;
      }
    }
  }

  return maxSum;
}
//Driver's code
int main() {

    vector<int> a = {1, 3, 8, -2, 6, -8, 5};
    cout << maximumSubarraySum(a) << endl;
    return 0;
}