# O(n) - Maximum Value Contiguous Subsequence

• 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)

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 */``````

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

• why do you need endJIdx and startJIdx?

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