Coding Ninja || Maximum Subarray Sum C++ Solution

 

Problem Statement

    Level: easy

You are given an array (ARR) of length N, consisting of integers. You have to find the sum of the subarray (including empty subarray) having maximum sum among all subarrays.
A subarray is a contiguous segment of an array. In other words, a subarray can be formed by removing 0 or more integers from the beginning, and 0 or more integers from the end of an array.

Approach:

A simple approach that comes to mind if you know is the Kadane’s algorithm.
Kadane's algorithm works on the idea of maintaining subarray sum at every iteration it becomes greater than the previous iteration. If the current Sum becomes negative than it is set to 0.

CODE:- 

#include long long maxSubarraySum(int arr[], int n) { long long currSum = 0; // Next we will be creating the maxSum element which will store the final // result of the code long long maxSum = INT_MIN; for(int i = 0; i < n; i++){ // running the for loop and adding up the value of the array elements currSum = currSum + arr[i]; // Here comes the twist of kadane's algorithm // If the cuurentSum becomes less than 0 then set it to 0; if(currSum < 0){ currSum = 0; } // Update the maxSum to the maximum of the previous iteration maxSum // and the cuurentSum in the current iteration maxSum = max(currSum, maxSum); } // finally returning the maxSum of trhe contigious sub array return maxSum; }

Time Complexity :- O(n)

Space Complexity :- O(1) 

   tthrth

Ti