To find the maximum sum subarray in an array using dynamic programming, we can use the Kadane's algorithm. The algorithm works by initializing two variables, max_ending_here and max_so_far, to the first element in the array. Then, we iterate through the array, updating these variables at each iteration.

  The max_ending_here variable keeps track of the maximum sum subarray ending at the current element. If adding the current element to the previous subarray sum results in a larger sum than the current element itself, we update max_ending_here accordingly. Otherwise, we set max_ending_here to the current element.

  The max_so_far variable keeps track of the maximum sum subarray seen so far. In each iteration, we compare max_ending_here with max_so_far and update max_so_far if necessary.

  Here is the step-by-step process:

  1. Initialize max_ending_here and max_so_far to the first element in the array.

  2. Iterate through the array starting from the second element.

  3. Update max_ending_here:

   - If max_ending_here + current element > current element, update max_ending_here.

   - Otherwise, set max_ending_here to the current element.

  4. Update max_so_far if max_ending_here is greater.

  5. Repeat steps 3-4 until the end of the array.

  6. Return max_so_far as the maximum sum subarray.

  The time complexity of this algorithm is O(n), where n is the length of the array, as we only need to iterate through the array once. Therefore, it is considered an efficient solution for finding the maximum sum subarray using dynamic programming.