{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:36:32Z","timestamp":1750307792705,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":31,"publisher":"ACM","license":[{"start":{"date-parts":[[2008,1,7]],"date-time":"2008-01-07T00:00:00Z","timestamp":1199664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2008,1,7]]},"DOI":"10.1145\/1328408.1328414","type":"proceedings-article","created":{"date-parts":[[2008,1,7]],"date-time":"2008-01-07T14:45:40Z","timestamp":1199717140000},"page":"31-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Maximum segment sum is back"],"prefix":"10.1145","author":[{"given":"Shin-Cheng","family":"Mu","sequence":"first","affiliation":[{"name":"Academia Sinica: Taiwan, Taipei, Taiwan Roc"}]}],"member":"320","published-online":{"date-parts":[[2008,1,7]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"287","volume-title":"Proceedings of the IFIP TC2\/WG2.1 Working Conference on Constructing Programs","author":"Backhouse R. C.","year":"1991","unstructured":"R. C. Backhouse , P. de Bruin , G. Malcolm , E. Voermans , and J. van der Woude. Relational catamorphisms. In B. M\u00f6ller, editor , Proceedings of the IFIP TC2\/WG2.1 Working Conference on Constructing Programs , pages 287 -- 318 . Elsevier Science Publishers , 1991 . R. C. Backhouse, P. de Bruin, G. Malcolm, E. Voermans, and J. van der Woude. Relational catamorphisms. In B. M\u00f6ller, editor, Proceedings of the IFIP TC2\/WG2.1 Working Conference on Constructing Programs, pages 287--318. Elsevier Science Publishers, 1991."},{"key":"e_1_3_2_1_2_1","volume-title":"Programming Pearls","author":"Bentley J.","year":"1986","unstructured":"J. Bentley . Programming Pearls . Addison-Wesley , 1986 . J. Bentley. Programming Pearls. Addison-Wesley, 1986."},{"key":"e_1_3_2_1_3_1","first-page":"3","volume-title":"Logic of Programming and Calculi of Discrete Design, number 36 in NATO ASI Series F","author":"Bird R. S.","year":"1987","unstructured":"R. S. Bird . An introduction to the theory of lists . In M. Broy, editor, Logic of Programming and Calculi of Discrete Design, number 36 in NATO ASI Series F , pages 3 -- 42 . Springer-Verlag , 1987 . R. S. Bird. An introduction to the theory of lists. In M. Broy, editor, Logic of Programming and Calculi of Discrete Design, number 36 in NATO ASI Series F, pages 3--42. Springer-Verlag, 1987."},{"key":"e_1_3_2_1_4_1","first-page":"287","volume-title":"Research Topics in Functional Programming","author":"Bird R. S.","year":"1990","unstructured":"R. S. Bird . A calculus of functions for program derivation . In D. A. Turner, editor, Research Topics in Functional Programming , University of Texas at Austin Year of Programming Series, pages 287 -- 308 . Addison-Wesley , 1990 . R. S. Bird. A calculus of functions for program derivation. In D. A. Turner, editor, Research Topics in Functional Programming, University of Texas at Austin Year of Programming Series, pages 287--308. Addison-Wesley, 1990."},{"key":"e_1_3_2_1_5_1","series-title":"International Series in Computer Science","volume-title":"Algebra of Programming","author":"Bird R. S.","year":"1997","unstructured":"R. S. Bird and Ode Moor . Algebra of Programming . International Series in Computer Science . Prentice Hall , 1997 . R. S. Bird and Ode Moor. Algebra of Programming. International Series in Computer Science. Prentice Hall, 1997."},{"key":"e_1_3_2_1_6_1","first-page":"281","volume-title":"Algebraic and Coalgebraic Methods in the Mathematics of Program Construction, number Lecture Notes in Computer Science 2297","author":"Bird R. S.","year":"2002","unstructured":"R. S. Bird , J. Gibbons , and S.-C. Mu . Algebraic methods for optimization problems . In R. C. Backhouse, R. Crole, and J. Gibbons, editors, Algebraic and Coalgebraic Methods in the Mathematics of Program Construction, number Lecture Notes in Computer Science 2297 , pages 281 -- 307 . Springer-Verlag , January 2002 . R. S. Bird, J. Gibbons, and S.-C. Mu. Algebraic methods for optimization problems. In R. C. Backhouse, R. Crole, and J. Gibbons, editors, Algebraic and Coalgebraic Methods in the Mathematics of Program Construction, number Lecture Notes in Computer Science 2297, pages 281--307. Springer-Verlag, January 2002."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11428848_108"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/165180.165225"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_15"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704440430"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/265779.265782"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2003.09.001"},{"key":"e_1_3_2_1_13_1","volume-title":"Een methode van programmeren","author":"Dijkstra E. W.","year":"1984","unstructured":"E. W. Dijkstra and W. H. J. Feijen . Een methode van programmeren . Academic Service , 's Gravenhage, the Netherlands, 1984 . E. W. Dijkstra and W. H. J. Feijen. Een methode van programmeren. Academic Service, 's Gravenhage, the Netherlands, 1984."},{"key":"e_1_3_2_1_14_1","series-title":"Lecture Notes in Computer Science 2759","first-page":"46","volume-title":"Proceedings of the 8th International Conference on Implementation and Application of Automata","author":"Fan T.-H.","year":"2003","unstructured":"T.-H. Fan , SLee, H.-I. Lu , T.-S. Tsou , T.-C. Wang , and A. Yao . An optimal algorithm for maximum-sum segment and its application in bioinformatics . In Proceedings of the 8th International Conference on Implementation and Application of Automata , Lecture Notes in Computer Science 2759 , pages 46 -- 66 . Springer-Verlag , July 2003 . T.-H. Fan, SLee, H.-I. Lu, T.-S. Tsou, T.-C. Wang, and A. Yao. An optimal algorithm for maximum-sum segment and its application in bioinformatics. In Proceedings of the 8th International Conference on Implementation and Application of Automata, Lecture Notes in Computer Science 2759, pages 46--66. Springer-Verlag, July 2003."},{"key":"e_1_3_2_1_15_1","first-page":"11","volume-title":"Workshop on Algorithm Engineering (WAE 97)","author":"Futamura Y.","year":"1997","unstructured":"Y. Futamura , C. Shirai , Y. Liu , N. Futamura , and K. Kakehi . Data structures for solving programming problems concerning segments in a sequence . In Workshop on Algorithm Engineering (WAE 97) , pages 11 -- 13 , 1997 . Y. Futamura, C. Shirai, Y. Liu, N. Futamura, and K. Kakehi. Data structures for solving programming problems concerning segments in a sequence. In Workshop on Algorithm Engineering (WAE 97), pages 11--13, 1997."},{"key":"e_1_3_2_1_16_1","volume-title":"New Zealand Formal Program Development Colloquium Seminar","author":"Gibbons J.","year":"1994","unstructured":"J. Gibbons . An introduction to the Bird-Meertens formalism . New Zealand Formal Program Development Colloquium Seminar , Hamilton , November 1994 . J. Gibbons. An introduction to the Bird-Meertens formalism. New Zealand Formal Program Development Colloquium Seminar, Hamilton, November 1994."},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of ISRG\/SERG Research Colloquium","author":"Gibbons J.","year":"1997","unstructured":"J. Gibbons . Calculating functional programs . In Proceedings of ISRG\/SERG Research Colloquium . Oxford Brookes University , November 1997 . J. Gibbons. Calculating functional programs. In Proceedings of ISRG\/SERG Research Colloquium. Oxford Brookes University, November 1997."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/645907.673125"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.08.001"},{"key":"e_1_3_2_1_20_1","first-page":"33","volume-title":"Formal Development Programs and Proofs","author":"Gries D.","year":"1989","unstructured":"D. Gries . The maximum-segment-sum problem. In E. W. Dijkstra, editor, Formal Development Programs and Proofs , University of Texas at Austin Year of Programming Series, pages 33 -- 36 . Addison-Wesley , 1989 . D. Gries. The maximum-segment-sum problem. In E. W. Dijkstra, editor, Formal Development Programs and Proofs, University of Texas at Austin Year of Programming Series, pages 33--36. Addison-Wesley, 1989."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01182773"},{"key":"e_1_3_2_1_22_1","volume-title":"Programming: the Derivation of Algorithms","author":"Kaldewaij A.","year":"1990","unstructured":"A. Kaldewaij . Programming: the Derivation of Algorithms . Prentice Hall , 1990 . A. Kaldewaij. Programming: the Derivation of Algorithms. Prentice Hall, 1990."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2006.06.002"},{"key":"e_1_3_2_1_24_1","series-title":"Lecture Notes in Computer Science 2420","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/3-540-45687-2_38","volume-title":"Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science","author":"Lin Y.-L.","year":"2002","unstructured":"Y.-L. Lin , T. Jiang , and K.-M. Chao . Efficient algorithms for locating the length-constrained heaviest segments, with applications to biomolecular sequence analysis . In Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science , Lecture Notes in Computer Science 2420 , pages 459 -- 470 . Springer-Verlag , 2002 . Y.-L. Lin, T. Jiang, and K.-M. Chao. Efficient algorithms for locating the length-constrained heaviest segments, with applications to biomolecular sequence analysis. In Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 2420, pages 459--470. Springer-Verlag, 2002."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/503032.503041"},{"key":"e_1_3_2_1_26_1","volume-title":"University of Tokyo","author":"Maehara T.","year":"2007","unstructured":"T. Maehara .( Formalization and Application of the Windowing Technique based on Program Calculation). Bachelor's Thesis (in Japanese) , University of Tokyo , February 2007 . T. Maehara.(Formalization and Application of the Windowing Technique based on Program Calculation). Bachelor's Thesis (in Japanese), University of Tokyo, February 2007."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(88)90023-8"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792034.1792041"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/351240.351254"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(90)90045-F"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(92)90033-8"}],"event":{"name":"PEPM08: Partial Evaluation and Program Manipulation","sponsor":["SIGPLAN ACM Special Interest Group on Programming Languages","ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"San Francisco California USA","acronym":"PEPM08"},"container-title":["Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328408.1328414","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1328408.1328414","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:22Z","timestamp":1750254982000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328408.1328414"}},"subtitle":["deriving algorithms for two segment problems with bounded lengths"],"short-title":[],"issued":{"date-parts":[[2008,1,7]]},"references-count":31,"alternative-id":["10.1145\/1328408.1328414","10.1145\/1328408"],"URL":"https:\/\/doi.org\/10.1145\/1328408.1328414","relation":{},"subject":[],"published":{"date-parts":[[2008,1,7]]},"assertion":[{"value":"2008-01-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}