Some doubts regarding Kadane's Algorithm for maximum sum subarray

#1

Here are all my doubts:

  1. How to get the start and end index of the subarray to which the maximum sum in the output is referring to?
  2. if all the elements in the array are negative, then the algo will return zero… but there is not any subarray of lenght zero. In this case, the answer must be the largest element of the array
  3. Can we modify the algorithm in some way to get the minimum sum subarray of an array which has both positive and negative elements
#2

I just tried myself … others may see and give suggestions on the code written:
Answer to 1. https://repl.it/@sachin_yadav/Kadanes-max-sum-subaray-with-start-and-end
Answer to 3. https://repl.it/@sachin_yadav/Kadanes-algo-for-Minimum-sum-subarray
Answer to 2. The answer must be the greatest element of all negative elements (need someone’s suggestion here)

I posted the code using repl.it which i think is way more productive and everyone in my college (IIT Gandhinagar uses it for code saving and sharing

#3

Hi Sachin

  1. To get the start and end index of the maximum sum subarray, you can use two pointers start and end which will point to the start and end index of the resultant subarray. For this, you can update your program like this

     int max_so_far = INT_MIN, max_ending_here = 0, 
        start =0, end = 0, s=0; 
   
     for (int i=0; i< size; i++ ) 
     { 
         max_ending_here += a[i]; 
   
         if (max_so_far < max_ending_here) 
         { 
             max_so_far = max_ending_here; 
             start = s; 
             end = i; 
         } 
   
         if (max_ending_here < 0) 
         { 
             max_ending_here = 0; 
             s = i + 1; 
         } 
     }

  2. You can update your code for this too, if all the elements are negative then return the maximum of those negative elements.

  3. Yes you can modify this algorithm, to get minimum sum subarray too, just by taking the min of min_so_far and min_ending_here instead of taking the max of max_so_far and max_ending_here.

     int min_ending_here = INT_MAX, min_so_far = INT_MAX; 

     for (int i=0; i<n; i++) 
     { 
         if (min_ending_here > 0) {
             min_ending_here = arr[i]; 
          }
         else{
             min_ending_here += arr[i]; 
          }
         min_so_far = min(min_so_far, min_ending_here);             
     } 
     
     return min_so_far;
#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.