c++ - Is this the way the dynamic programming version of maximum subarray sum algorithm works? -

at dynamic programming chapter in algorithms textbook have example of how solve maximum sub array sum problem using technique. not sure if got idea behind algorithm describe here how think works (after reading several times , doing several examples).

basically, have array a of size n, , want find maximum sub array sum of array. sub array maximum sum can somewhere in right half of array, left half, or somewhere in middle. recursively call function compute maximum sub array sum left and, then, right side of array. then, compute maximum sub array sum middle of array end, compute maximum sub array sum middle beginning of array (it's length not n/2). then, if sum of maximum sub array sum form left plus maximum sub array sum right bigger maximum sub array sum left half (the 1 computed recursively ) , maximum sub array sum right half (also computed recursively), maximum sub array sum in 1 in middle. otherwise maximum of 1 left half , 1 right half (those computed recursively).

did got working mechanism of algorithm?

this function analyzing:

int maxsubarraysum(int* arr, int n) {     if(n == 1)     {         return arr[0];     }     int m = n / 2;     int left = maxsubarraysum(arr, m);     int right = maxsubarraysum(arr + m, n - m);     int leftsum = int_min, rightsum = int_min, sum = 0;      for(int = m; < n; i++)     {         sum += arr[i];         rightsum = std::max(rightsum, sum);     }      sum = 0;      for(int = (m - 1); >= 0; i--)     {         sum += arr[i];         leftsum = std::max(leftsum, sum);     }      int retval = std::max(left, right);     return std::max(retval, leftsum + rightsum);     }   

one not need recursion achieve dynamic programming. kadane's algorithm simple example of dynamic programming breaking down problem subproblems reused n-1 times (compare last far maximum sub array current 1 n-1 times).