0

I want to find the maximum sum of the given values in a given range, and the values chosen has to be contiguous and in complexity of O(logn) while calculating the sum. For example the input values are: 1 2 -100 3 4 and I want the maximum value from index 1 to 3 (index starts from 1), then the output will be:3 because 1+2=3. I know this question has been solved in a way using the array, you can look up in here

Now I have to complete it in complexity of O(logn)... What I can only think of is to build an AVL tree to save the values. But I don't exactly know how to find the max sum, since it has also to be contiguous. Does anyone have some ideas?

By using this I could find an max sum but not contiguous. I tried to fix it to satisfy that condition but I still can't.

btw my structure for the AVL tree is:

struct Node{
   int data;
   int height; //used to build AVL tree
   int index; //save the sequence of the input
   struct Node* left;
   struct Node* right;
}

int findMaxSum(struct Node* root, int x, int y)  //my function to find max sum (x y are my range index, from x to y)
{
    int Max, returnMax;
    if (root==NULL){
        return 0;
    }
    
    int left= findMaxSum(root->left, x, y);
    int right= findMaxSum(root->right, x, y);
    
    if (root->index>=x && root->index<=y && (preIndex==x || (root->index-1==preIndex))){      
        //preIndex is a global var to save the previous index 
        returnMax= max((max(left, right)+root->key), root->key);
        Max= max(returnMax, (left+right+root->key));
        
        if (Max>maxSum){                        
            maxSum= Max;    
            preIndex=root->index;   
        }   
                
    }
    else returnMax=root->key;
    
    return returnMax;
}

My actual input is to read some integers from the txt file:8 -4990 -9230 -3269 -2047 2875 3955 6022 8768 1 4 (8 means there will be 8 numbers to participate the calculation. 1 4means to choose the max sum between -4990 -9230 -3269 -2047 since index starts from 1).

My wrong output is: 1908 and the answer should be -2047. I think the problem of my code is that when I use recursive, my sum will accumulate the sums of every node(even the nodes that I don't want to count).

Is there another way of solving this or can it be fixed by adding conditions?

Betty Teng
  • 11
  • 2
  • This is a pretty well done post, but if you would include a [mcve] of your actual code version of _"this"_ directly into the edit window of pos, then describe where in that code your attempt failed to meet your expectations, it would be more clear. – ryyker Nov 19 '20 at 15:25
  • 1
    Ok! I'll add it up. Thanks for reminding! – Betty Teng Nov 19 '20 at 15:27
  • 1
    How can you scan an array in less than `O(n)` ? You surely have to scan all of it. Or you are not considering the preprocessing time (such as sorting the array or building the data structure first)? – Eugene Sh. Nov 19 '20 at 15:31
  • Keep in mind, that no matter how array data is conceptually thought of, it is always stored in a single block of contiguous memory. This fact allows an algorithms to determine whether two values are contiguous by evaluating the value of their indices. – ryyker Nov 19 '20 at 15:32
  • @EugeneSh. I mean only "calculating the sum" has to be ```O(logn)``` – Betty Teng Nov 19 '20 at 15:48
  • @ryyker can you explain it a little more? I don't really understand... – Betty Teng Nov 19 '20 at 15:51
  • Re “I mean only "calculating the sum" has to be O(logn)”: That does not make sense. Perhaps you envision some preparatory work being done and then the final result being found or calculated with some O(log n) operation. If so, you would have to give a clear specification of what is in the preparatory work and what is in the final work. And, since the maximum sum might be the entire sequence of n values, calculating it from those n values could still require O(n) work. So the preparatory work must include calculating sums, from which the final work plucks a result. That needs to be clarified. – Eric Postpischil Nov 19 '20 at 16:25
  • How is the "given range" specified? For example in your list of numbers `1 2 -100 3 4`, what is the "given range" and where does it come from? – Ian Abbott Nov 19 '20 at 16:51
  • If contiguity is a requirement, simply using indices will help to do that. BTW, contiguity seems to be in contention with (even diametrically opposed to) the other half of your requirement, i.e. that algorithm be complexity [O(log n)](https://stackoverflow.com/a/2307314/645128)), so it kind of seem futile. I will look forward to seeing a real solution to this. (by the way, the link provides some hints as to way I feel these two criteria makes this futile.) – ryyker Nov 19 '20 at 17:07
  • @EricPostpischil I read the txt file of a format looking like this: ```8``` ```-4990 -9230 -3269 -2047 2875 3955 6022 8768``` ```1 4```, so ```8```is my given range which means there'll be 8 numbers to do the calculation. ```1 4```is my maximum sum range which means I could only pick words from ```-4990 -9230 -3269 -2047``` and find a maximum sum (index starts counting from 1). – Betty Teng Nov 20 '20 at 01:24
  • @IanAbbott please see my last comment about reading the file – Betty Teng Nov 20 '20 at 01:25

0 Answers0