Longest Alternatin Subsequence DP MEMO STATE ITERATIVE

class Solution:
    def AlternatingaMaxLength(self, nums):
        dp={}
        #J--->True means go for increasing
        #j--->False means go for dereassing
        n=len(nums)
        def help(i,j):
            if i<0 or j<0 or i==n or j==n:return 0
            if (i,j) in dp:return dp[(i,j)]
            if j==True and nums[i]>nums[i-1]:
                    ans=max(1+help(i+1,False),help(i+1,True))
            elif j==False and nums[i]<nums[i-1]:
                    ans=max(1+help(i+1,True),help(i+1,False))
            else:
                ans=help(i+1,j)
            dp[(i,j)]=ans
            return ans
        return 1+max(help(1,True),help(1,False))
#iterative

class Solution:
    def AlternatingaMaxLength(self, nums):
        dp=[0]*(n)
        downs=[1]*n
        ups=[1]*n
        for i in range(1,n):
            for j in range(i):
                if nums[i]>nums[j]:
                    ups[i]=max(ups[i],1+downs[j])
                elif nums[i]<nums[j]:
                    downs[i]=max(downs[i],1+ups[j])
        return max(ups[-1],downs[-1])

#O(1) state approach

class Solution:
    def AlternatingaMaxLength(self, nums):
        ups=downs=1
        '''
        This problem boils to find no of max(hills, valleys) in the given graph.
        This is Greedy approach
        Watch a youtube video
        In increasing sequence T you always select the greatest element of T so that you can have
        the chance of more least elements of next sequence.---->No of ups

        In Decreasing sequence T you always select the lowest element of T so that you can have
        the chance of more greater elements of next sequence.--->No of downs
        '''
        for i in range(1,n):
            if nums[i]>nums[i-1]:
                ups=downs+1
            #ignore nums[i]==nums[i-1] because theya are not in alternative
            #subseqeunce
            elif nums[i]<nums[i-1]:
                downs=ups+1
        return max(ups,downs)