O(n) - Maximum Value Contiguous Subsequence


  • 0
    J

    Maximum Value Contiguous Subsequence.

    Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i) ... A(j) for which the sum of elements in the subsequence is maximized.

    Example-1:

    Array - {1,-2,4,3,-2,0}

    Output:
    (4,3) -> 7 // Here 7 is the maximum sum of elements.

    Example-2:

    Array = {1,2,4,3,-2,20};

    Output:
    (1,2,4,3,-2,20) -> 28

    Example-3:

    Array = {1,0,-4,0,0,0};

    Output: (1) -> 1


    big(o) ==> O(n)


    0_1467653851270_ddd.png

    Solution:

    #ifndef DynamicProgramming_h
    #define DynamicProgramming_h
    #include <assert.h>     /* assert */
    
    int maxValueOfElements(int arr[], int length, int *startIdx, int *endIdx){
        
        *startIdx = *endIdx = 0; // Reset start / end index with ZERO.
        
        if(length == 0)
            return arr[0]; // Return by setting startIdx and endIdx ZERO.
        else if(length < 0)
            assert(length >= 0); // Give assert if user pass <0 value in length.
        
        int j=1, maxSubEleJ_Minus1=arr[0], maxSubEle=arr[0], endJIdx=0, startJIdx=0;
        
        do{
            if(maxSubEleJ_Minus1 + arr[j] > arr[j])
            {
                maxSubEleJ_Minus1 = maxSubEleJ_Minus1   + arr[j];
                if(maxSubEle < maxSubEleJ_Minus1)
                {
                    maxSubEle=maxSubEleJ_Minus1;
                    *endIdx = j;
                }
                endJIdx = j;
            }
            else
            {
                maxSubEleJ_Minus1 = arr[j];
                if(maxSubEle < maxSubEleJ_Minus1)
                {
                    maxSubEle=maxSubEleJ_Minus1;
                    // Reset with Jth index as arr[j] index is the Max element.
                    *startIdx = *endIdx = j; 
                }
                // Reset with Jth index as arr[j] index is the Max element.
                startJIdx = endJIdx = j; 
            }
        }while(++j < length);
        
        return maxSubEle;
    }
    #endif /* DynamicProgramming_h */

  • 0
    D

    did they ask you on phone ? is it a coding challenge?


  • 0
    D

    why do you need endJIdx and startJIdx?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.