We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. C++
  3. STL
  4. Deque-STL
  5. Discussions

Deque-STL

  • kmiklas1
     + 7 comments

    If you are getting timeouts (little red circles), you must optimize your code. Note that a loop within a loop (On^2) is too expensive and slow; it will fail.

    The trick is to use the max of the previous range. It can be compared to the endpoints of the new range to save a lot of time:

        // a       b 
    // 4 5 6 2 3 5 6 7 8 4 3 2 4 5 6 7
    // max is 6 at position 2
    // slide range forward one
        
    //   a       b 
    // 4 5 6 2 3 5 6 7 8 4 3 2 4 5 6 7
    // just two checks:
    // 1. Did the max go out of range? Was it at position a-1?
    // 2. Is the new value at b greater than the max?
    // No, no; Max is still 6 at position 2.
    // print it, and move on. Cheap! :^)

    Great question, Hackerrank!