Thursday, June 30, 2016

We were discussing maximum sum rectangle in a 2d array. There is a technique called Kadane's algorithm that we can use to find this sum. The algorithm returns the maximum sum  and stores the starting and ending indexes
int kadane(List<int>num, ref int start, ref int end, int n)
{
int sum = 0;
int max = INT_MIN;
end = -1;
int cur = 0,
for (int i = 0; i < n; i++)
{
  sum += num[i];
  if sum < 0){
     sum = 0;
     cur =  i + 1;
}else if (sum > max ){
   max = sum;
   start  = cur;
   end  = i;
}
}
if (end != -1)
    return max;
max = num[0];
start = 0;
end = 0;
// find the max element
for (int i = 1; i < n; i++)
  if (num[i] > max){
      max = num[i];
      start = i;
      end = i;
   }
return max;
}
This can also be written as
def max_subarray(A):
      max_ending_here = max_so_far = 0;
      for x in A:
           max_ending_here = max(0, max_ending_here+x)
           max_so_far = max(max_so_far, max_ending_here)
      return max_so_far
#courtesy online resources

No comments:

Post a Comment