[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Selecting Sums in Arrays

  • Conference paper
Algorithms and Computation (ISAAC 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5369))

Included in the following conference series:

  • 1622 Accesses

Abstract

In an array of n numbers each of the \(\binom{n}{2}+n\) contiguous subarrays define a sum. In this paper we focus on algorithms for selecting and reporting maximal sums from an array of numbers. First, we consider the problem of reporting k subarrays inducing the k largest sums among all subarrays of length at least l and at most u. For this problem we design an optimal O(n + k) time algorithm. Secondly, we consider the problem of selecting a subarray storing the k’th largest sum. For this problem we prove a time bound of Θ(n · max {1,log(k/n)}) by describing an algorithm with this running time and by proving a matching lower bound. Finally, we combine the ideas and obtain an O(n· max {1,log(k/n)}) time algorithm that selects a subarray storing the k’th largest sum among all subarrays of length at least l and at most u.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Allison, L.: Longest biased interval and longest non-negative sum interval. Bioinformatics 19(10), 1294–1295 (2003)

    Article  Google Scholar 

  2. Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: Basic local alignment search tool. Journal of Molecular Biology 215(3), 403–410 (1990)

    Article  Google Scholar 

  3. Arge, L., Vitter, J.S.: Optimal external memory interval management. SIAM Journal on Computing 32(6), 1488–1508 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bae, S.E., Takaoka, T.: Algorithms for the problem of k maximum sums and a vlsi algorithm for the k maximum subarrays problem. In: Proc. 7th International Symposium on Parallel Architectures, Algorithms, and Networks, pp. 247–253. IEEE Computer Society, Los Alamitos (2004)

    Google Scholar 

  5. Bentley, J.: Programming pearls: algorithm design techniques. Commun. ACM 27(9), 865–873 (1984)

    Article  Google Scholar 

  6. Blum, M., Floyd, R.W., Pratt, V.R., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Syst. Sci. 7(4), 448–461 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  7. Brodal, G.S., Jørgensen, A.G.: A linear time algorithm for the k maximal sums problem. In: Kučera, L., Kučera, A. (eds.) MFCS 2007. LNCS, vol. 4708, pp. 442–453. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  8. Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. Journal of Computer and System Sciences 38(1), 86–124 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  9. Fan, T.-H., Lee, S., Lu, H.-I., Tsou, T.-S., Wang, T.-C., Yao, A.: An optimal algorithm for maximum-sum segment and its application in bioinformatics. In: Proc. 8th International Conference on Implementation and Application of Automata. LNCS, pp. 46–66. Springer, Heidelberg (2003)

    Google Scholar 

  10. Frederickson, G.N.: An optimal algorithm for selection in a min-heap. Inf. Comput. 104(2), 197–214 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  11. Frederickson, G.N., Johnson, D.B.: The complexity of selection and ranking in X+Y and matrices with sorted columns. J. Comput. Syst. Sci. 24(2), 197–208 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  12. Fukuda, T., Morimoto, Y., Morishita, S., Tokuyama, T.: Data mining with optimized two-dimensional association rules. ACM Trans. Database Syst. 26(2), 179–213 (2001)

    Article  MATH  Google Scholar 

  13. Fukuda, T., Morimoto, Y., Morishta, S., Tokuyama, T.: Interval finding and its application to data mining. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E80-A(4), 620–626 (1997)

    Google Scholar 

  14. Hannenhalli, S., Levy, S.: Promoter prediction in the human genome. Bioinformatics 17, S90–S96 (2001)

    Article  Google Scholar 

  15. Huang, X.: An algorithm for identifying regions of a DNA sequence that satisfy a content requirement. Computer Applications in the Biosciences 10(3), 219–225 (1994)

    Google Scholar 

  16. Lin, T.-C., Lee, D.T.: Efficient algorithms for the sum selection problem and k maximum sums problem. In: The 17th International Symposium on Algorithms and Computation. LNCS, pp. 460–473. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  17. Lin, T.-C., Lee, D.T.: Randomized algorithm for the sum selection problem. Theor. Comput. Sci. 377(1-3), 151–156 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  18. Lin, Y.-L., Jiang, T., Chao, K.-M.: Efficient algorithms for locating the length-constrained heaviest segments, with applications to biomolecular sequence analysis. In: Proc. 27th International Symposium of Mathematical Foundations of Computer Science 2002. LNCS, pp. 459–470. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  19. Nievergelt, J., Reingold, E.M.: Binary search trees of bounded balance. In: STOC 1972: Proceedings of the fourth annual ACM symposium on Theory of computing, pp. 137–142. ACM, New York (1972)

    Chapter  Google Scholar 

  20. Okasaki, C.: Purely functional random-access lists. In: Functional Programming Languages and Computer Architecture, pp. 86–95 (1995)

    Google Scholar 

  21. Takaoka, T.: Efficient algorithms for the maximum subarray problem by distance matrix multiplication. Electr. Notes Theor. Comput. Sci. 61 (2002)

    Google Scholar 

  22. Tamaki, H., Tokuyama, T.: Algorithms for the maximum subarray problem based on matrix multiplication. In: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, pp. 446–452. Society for Industrial and Applied Mathematics, Philadelphia (1998)

    Google Scholar 

  23. Walder, R.Y., Garrett, M.R., McClain, A.M., Beck, G.E., Brennan, T.M., Kramer, N.A., Kanis, A.B., Mark, A.L., Rapp, J.P., Sheffield, V.C.: Short tandem repeat polymorphic markers for the rat genome from marker-selected libraries. Mammalian Genome 9(12), 1013–1021 (1998)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. BRICS, MADALGO, Department of Computer Science, University of Aarhus, Denmark

    Gerth Stølting Brodal & Allan Grønlund Jørgensen

Authors
  1. Gerth Stølting Brodal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Allan Grønlund Jørgensen
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Information Technologies, University of Sydney, Australia

    Seok-Hee Hong

  2. Graduate School of Informatics, Kyoto University, 606-8501, Kyoto, Japan

    Hiroshi Nagamochi

  3. Graduate School of Informatics, Kyoto University, Japan

    Takuro Fukunaga

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Brodal, G.S., Jørgensen, A.G. (2008). Selecting Sums in Arrays. In: Hong, SH., Nagamochi, H., Fukunaga, T. (eds) Algorithms and Computation. ISAAC 2008. Lecture Notes in Computer Science, vol 5369. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92182-0_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-92182-0_12

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-92181-3

  • Online ISBN: 978-3-540-92182-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation