Max Subarray sum

Jyothi
2 min readJun 5, 2024

--

Problem:

Dynamic programming solution using Kadane’s algorithm:

#define max(a,b) a>b? a: b
int maxSubArray(int* nums, int numsSize) {
/* Subarray can be the complete array or any part of the array
nums = [5, 4, -1, 7, 8]
subarrays for it are [5], [5,4], [5,4,-1], [5,4,-1,7],
[5,4,-1,7,8], [4], [4,-1], [4,-1,7], [4,-1,7,8], [-1],
[-1,7],[-1,7,8], [7], [7,8], [8], []
Brute force approach for checking the max sum of sub array is:
ii= 0 till len(nums)-1 that is going over nums[0] till nums[last]
initialise the current subarray =[]
jj= ii till last element-index
adding nums[jj] to current subarray
checking the sum of this current subarray and assign it to
maxvalue
These two loops generate the above-mentioned subarrays
ii=0 :::: jj=0 [5]; jj=1 [5,4]; jj=2 [5,4,-1]...; jj=4 [5,4,-1,7,8]
ii=1 :::: jj=1 [4]; ......jj=4 [4,-1,7,8]
....
ii=4 :::: jj=4 [8]

For dynamic programming, we should use Kadane's algorithm.
Check the current sum with the current element and sum of
previous elements
Assign the max value of (current element, curr_sum+current element)
to curr_sum

max_val = max(max_val, curr_sum)
*/
int curr_sum = nums[0];
int max_sum = nums[0];
for (int ii =1; ii<numsSize; ii++){
curr_sum = max(nums[ii], nums[ii]+curr_sum);
if (curr_sum > max_sum)
max_sum = curr_sum;
}
return max_sum;
}

--

--