please provide the optimal solution with the provement but not code

3. You are given a boolean expression consisting of a string of the symbols 'true', 'false', 'and', 'or, and Xor. Count the number of ways to parenthesize the expression such that it will evaluate to true. For example, there is only 1 way to parenthesize 'true and false xor true' such that it evaluates to true. Give a dynamic programming algorithm to solve this problem and analyze the time complexity of your algorithm. 4. The input to this problem is a sequence S of n integers (not necessarily positive). The problem is to find the consecutive subsequence of S with maximum sum. Consecutive means that you are not allowed to skip numbers. For example if the input was 12,-14,1,23, -6,22, -34,13, the output would be 1,23. -6,22. Give a linear time algorithm for this problem. 3. You are given a boolean expression consisting of a string of the symbols 'true', 'false', 'and', 'or, and Xor. Count the number of ways to parenthesize the expression such that it will evaluate to true. For example, there is only 1 way to parenthesize 'true and false xor true' such that it evaluates to true. Give a dynamic programming algorithm to solve this problem and analyze the time complexity of your algorithm. 4. The input to this problem is a sequence S of n integers (not necessarily positive). The problem is to find the consecutive subsequence of S with maximum sum. Consecutive means that you are not allowed to skip numbers. For example if the input was 12,-14,1,23, -6,22, -34,13, the output would be 1,23. -6,22. Give a linear time algorithm for this