Recursive, Divide-and-conquer algorithm for longest non-decreaseing array of numbers

I'm having some serious problems for this problem. I need an recursive algorithm that "divides and conquers" that tells me the length for the longest non-decreasing array of numbers. Personally, I would choose to use this code that I wrote before reading the question carefully.

 int bestIndex = 0;
    int bestLength = 0;
    int curIndex = 0;
    int curLength = 1;

    for (int i = 1; i < a.length; i ++){
        if (a[i] >= a[i-1]){
            curLength ++;
        }else {
            curLength = 1;
            curIndex = i;
        }
        if (curLength > bestLength){
            bestIndex = curIndex;
            bestLength = curLength;
        }
    }
    return bestLength;

The problem is that the 开发者_如何学Pythonassignment requires me to use divide and conquer and i can't think of a method to do it.

An example is "4 2 3 3 1 2 4 5 9 2" It would return "5" because of "1 2 4 5 9"

Any help is greatly appreciated.

Thanks

Are you sure the subarrays need to consist of contiguous elements? This problem gets way more interesting for subsequences...

Anyway, if you need a divide and conquer algorithm try to follow the basic blueprint:

function f(array) =
    if array is empty or constant size or something like that
        handle base case
    else
        result1 <- f(first half of the array)
        result2 <- f(second half of the array)
        return some_way_to_combine(result1, result2)

Of course, you need to correctly choose what f should return to help you out. You will need to handle both the cases where the increasing subarray is inside one of the halves ond the case where it crosses the boundary.

The other answer is a good generic answer.

However, I'm going to suggest that the key is knowing what questions you need to be able to answer when combining results. If result 1 represents array [i,j] and result 2 represents [j+1,k] then these are the questions you need to be able to answer:

• What is the longest non-decreasing sequence that ends at j?
• What is the longest non-decreasing sequence that starts at j+1?
• What is the maximum length sequence I've seen thus far (including the sequences that end at j and start at j+1)?

If you assume you can already answer these questions for result1 and result2 then you should be able to define answers for your combined result [i, k] (i.e. longest sequence that starts at i, and longest that starts at k, as well as the longest you've ever seen thus far including those two).