28{
32
33 const std::string max_subarray_sum_program =
34 " var zero := 0; "
35 " var curr_sum := 0; "
36 " var curr_start := 0; "
37 " "
38 " for (var i := 0; i < vec[]; i += 1) "
39 " { "
40 " curr_sum += vec[i]; "
41 " "
42 " if (curr_sum < zero) "
43 " { "
44 " curr_sum := 0; "
45 " curr_start := i + 1; "
46 " } "
47 " else if (curr_sum > max_sum) "
48 " { "
49 " max_sum := curr_sum; "
50 " max_start := curr_start; "
51 " max_end := i; "
52 " } "
53 " } ";
54
55 T max_sum = T(0);
56 T max_start = T(0);
57 T max_end = T(0);
58
59 T vec[] = { T(-1), T(-2), T(3), T(5), T(6), T(-2), T(-1), T(4), T(-4), T(2), T(-1) };
60
61 symbol_table_t symbol_table;
62
63 symbol_table.add_variable("max_sum" , max_sum );
64 symbol_table.add_variable("max_start", max_start);
65 symbol_table.add_variable("max_end" , max_end );
66 symbol_table.add_vector ("vec" , vec );
67
68 expression_t expression;
69 expression.register_symbol_table(symbol_table);
70
71 parser_t parser;
72 parser.compile(max_subarray_sum_program,expression);
73
74 expression.value();
75
76 if (max_start <= max_end)
77 {
78 printf("Max sum: %10.3f \n", max_sum);
79 printf("Start index: %4d\n", static_cast<int>(max_start));
80 printf("End index: %4d\n", static_cast<int>(max_end ));
81
82 for (int i = static_cast<int>(max_start); i <= static_cast<int>(max_end); ++i)
83 {
84 printf("%5.3f ",vec[i]);
85 }
86
87 printf("\n");
88 }
89 else
90 printf("No maximum sum found.\n");
91}
