Блог пользователя Tintin

How can I implement it O(n)?
Автор Tintin, 13 лет назад, По-английски

Your text to link here... My dp solution is O(n^2) but here n=50000 and time is 1 sec. Is there any mathematical formula which reduces time within 1 sec. Any hints...Thanks

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Try this idea: calculate sums in all prefixes (from empty to the whole sequence) and then sum of elements in a some substring is difference of two numbers. Hope this helps. If not, I can give you detailed solution.

→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I don't get it properly.

    → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Look: you have an array: 1 2 3 4 5. It has the following prefixes: "", "1", "1 2", and so on. You calculate sum of numbers in each such prefix and get 0, 1, 1+2=3, 1+2+3=6, 10 and 15 (let's call it s[]). Then, to calculate, for example, sum from 2 to 4, you just calculate s[4] - s[1]=9. Elements before 2 were reduced.

      This idea can help you solving this problem: you run down left border of a substring and then you can calc amount of required substrings in O(1) for each left border.

      → Ответить