CODEWITHSUNDEEP
algorithmpalindromedivide-and-conquer
Nitish Upreti
Nitish Upreti

Reputation: 6550

Why we cannot solve Longest Palindrome Subsequence by Divide and Conquer?

Given an array string, find the longest substring which is palindrome. For example, if the given string is “forgeeksskeegfor”, the output should be "geeksskeeg".

The problem has an efficient solution with Dynamic Programming.

However, I was just wondering why cant we solve the problem with Divide and Conquer in a similar way we solve the Maximum Subarray problem. (http://en.wikipedia.org/wiki/Maximum_subarray_problem )

We formulate the maximum subarray problem to be efficiently solved with D&C:

1) Divide the given array in two halves 2) Return the maximum of following three ….a) Maximum subarray sum in left half (Make a recursive call) ….b) Maximum subarray sum in right half (Make a recursive call) ….c) Maximum subarray sum such that the subarray crosses the midpoint

The longest Palindrome subsequence problem can be though of as :

1) Divide the given array in two halves 2) Return the maximum of following three ….a) Maximum palindrome sum in left half (Make a recursive call) ….b) Maximum palindrome sum in right half (Make a recursive call) ….c) Maximum palindrome sum such that the subarray crosses the midpoint

We could think about an implementation and say a solution does not exists,but what about the problem structure stops us from thinking a D&C solution?

Upvotes: 1

Views: 1286

Answers (1)

Rhugweda
Rhugweda

Reputation: 1

The approach of Divide and Conquer might work if the string is of the form "13267224". Here, 6+2+3 = 11 and 7+2+2 = 11 Hence, "326722" is the longest palindromic sum substring. But in the case of character strings eg. "abaccidba", Divide and Conquer won't work.

Upvotes: 0

Related Questions