Sunday 3 January 2016

Longest sub array that has elements in increasing order?

Increasing longest sub array

We can solve it by using:

Brute force – Time Complexity O(n^2)
Dynamic programming - Time Complexity O(n).

Pseudo code:


def DP(a[]):
            dp[1] = 1
            for i = 2 to n:
                    if a[i] > a[i - 1]:
                            dp[i] = dp[i - 1] + 1
                    else:
                            dp[i] = 1

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...