(original) (raw)

/* ************************************************************** * C++ Mathematical Expression Toolkit Library * * * * ExprTk Maximum Subarray Problem * * Author: Arash Partow (1999-2024) * * URL: https://www.partow.net/programming/exprtk/index.html * * * * Copyright notice: * * Free use of the Mathematical Expression Toolkit Library is * * permitted under the guidelines and in accordance with the * * most current version of the MIT License. * * https://www.opensource.org/licenses/MIT * * SPDX-License-Identifier: MIT * * * ************************************************************** */ #include #include #include "exprtk.hpp" template void max_subarray_sum() { typedef exprtk::symbol_table symbol_table_t; typedef exprtk::expression expression_t; typedef exprtk::parser parser_t; const std::string max_subarray_sum_program = " var zero := 0; " " var curr_sum := 0; " " var curr_start := 0; " " " " for (var i := 0; i < vec[]; i += 1) " " { " " curr_sum += vec[i]; " " " " if (curr_sum < zero) " " { " " curr_sum := 0; " " curr_start := i + 1; " " } " " else if (curr_sum > max_sum) " " { " " max_sum := curr_sum; " " max_start := curr_start; " " max_end := i; " " } " " } "; T max_sum = T(0); T max_start = T(0); T max_end = T(0); T vec[] = { T(-1), T(-2), T(3), T(5), T(6), T(-2), T(-1), T(4), T(-4), T(2), T(-1) }; symbol_table_t symbol_table; symbol_table.add_variable("max_sum" , max_sum ); symbol_table.add_variable("max_start", max_start); symbol_table.add_variable("max_end" , max_end ); symbol_table.add_vector ("vec" , vec ); expression_t expression; expression.register_symbol_table(symbol_table); parser_t parser; parser.compile(max_subarray_sum_program,expression); expression.value(); if (max_start <= max_end) { printf("Max sum: %10.3f \n", max_sum); printf("Start index: %4d\n", static_cast(max_start)); printf("End index: %4d\n", static_cast(max_end )); for (int i = static_cast(max_start); i <= static_cast(max_end); ++i) { printf("%5.3f ",vec[i]); } printf("\n"); } else printf("No maximum sum found.\n"); } int main() { max_subarray_sum(); return 0; }