The "Kadane's algorithm" is a well-known algorithm used to find the maximum sum of a contiguous subarray within an array of numbers. It efficiently solves the "maximum subarray problem" and is named after its inventor, Jay Kadane.

The algorithm works by iteratively scanning the array from left to right, maintaining two variables:

`currentSum`

and `maxSum`

. The `currentSum`

variable keeps track of the sum of the subarray seen so far, while `maxSum`

stores the maximum sum encountered during the traversal.Here's an in-depth explanation of how Kadane's algorithm works:

- Initialize
`currentSum`

and`maxSum`

to the first element of the array. `currentSum`

=`maxSum`

= array[0]

- Iterate through the array from the second element (index 1) to the end.
- For each element
`num`

at index`i`

, calculate the new`currentSum`

as the maximum value between: `num`

alone (starting a new subarray) or`num`

combined with the previous`currentSum`

(extending the existing subarray).- Update
`maxSum`

if the new`currentSum`

is greater than the previous`maxSum`

. `maxSum = max(maxSum, currentSum)`

`currentSum = max(num, currentSum + num)`

- After iterating through the entire array,
`maxSum`

will hold the maximum sum of any contiguous subarray.

- Return
`maxSum`

as the result.

The key idea behind Kadane's algorithm is the observation that, at each step, we only need to consider the maximum sum obtained by either starting a new subarray or extending the previous subarray. By keeping track of the maximum sum encountered so far (

`maxSum`

), we can find the overall maximum subarray sum efficiently.The time complexity of Kadane's algorithm is O(n), where n is the size of the input array, as it involves a single pass through the array. The space complexity is O(1) since it uses only a constant amount of additional space to store the variables

`currentSum`

and `maxSum`

.Kadane's algorithm is a

**dynamic programming algorithm**used to find the maximum subarray sum in a given array of integers. In C++, you can implement Kadane's algorithm using the following code:`#include<bits/stdc++.h> using namespace std; int kadane(vector<int>& nums) { int n = nums.size(); int max_sum = INT_MIN; int curr_sum = 0; for(int i=0; i<n; i++) { curr_sum += nums[i]; if(curr_sum > max_sum) max_sum = curr_sum; if(curr_sum < 0) curr_sum = 0; } return max_sum; } int main() { int n; cin >> n; vector<int> nums(n); for(int i=0; i<n; i++) cin >> nums[i]; int result = kadane(nums); cout << "The maximum subarray sum is " << result << endl; return 0; }`

In this code, the

`kadane()`

function takes a vector of integers `nums`

as input and returns the maximum subarray sum. The function initializes three variables: `n`

which is the size of the input array `nums`

, `max_sum`

which is initialized to the minimum value of integer, and `curr_sum`

which is initialized to 0.In the

`for`

loop, the function iterates through each element of `nums`

and adds the element to `curr_sum`

. Then, it checks if `curr_sum`

is greater than `max_sum`

. If it is, `max_sum`

is updated to `curr_sum`

.Next, the function checks if

`curr_sum`

is less than 0. If it is, `curr_sum`

is reset to 0, since any subarray containing a negative sum could not be the maximum subarray.Finally, the function returns

`max_sum`

, which is the maximum subarray sum.In the

`main()`

function, the user inputs the size of the array `n`

and each element of the array `nums`

. The `kadane()`

function is then called to find the maximum subarray sum, which is outputted to the console.Time Complexity:
Kadane's algorithm has a time complexity of O(n), where n is the size of the input array. The algorithm performs a single pass through the array, visiting each element once. Therefore, the runtime grows linearly with the size of the input.

Space Complexity:
The space complexity of Kadane's algorithm is O(1) or constant space. The algorithm only requires a few variables to keep track of the maximum sum and current sum. Regardless of the input array size, the algorithm uses a fixed amount of additional space, resulting in constant space complexity.

To summarize:

- Time Complexity:
`O(n)`

(linear time)

- Space Complexity:
`O(1)`

(constant space)

**PRACTICE PROBLEMS :**