Let $$$A$$$ be an array of positive integers. Let you are playing a Game.
Initially your score is $$$0$$$.
Let you start from index $$$0$$$. In one move you can go from current cell $$$i$$$ to any adjacent cell i.e (either $$$i-1$$$ or $$$i+1$$$ if they exist). you can visit a cell any number of times. when you visit any cell $$$i$$$, then $$$A[i]$$$ is added in your score.
you should make exactly $$$k$$$ such moves.
what is the maximum possible value of score?

Example
if arr is $$$[7, 8, 7 ,9 , 5]$$$
and $$$k = 4$$$, then ans is $$$38$$$
i.e you can move like this : $$$0 -> 1 -> 2 -> 3 -> 2$$$

Constraint:
$$$k < 10^6$$$
$$$N < 10^6$$$
$$$A[i] < 10^6$$$

The best i can think of it's $$$O(n*k)$$$ solution using dynamic programming, which definitely times out.

1. Given an undirected weighted graph and two node s, t. How one can print any simple cycle that passes through both s and t or say no such cycle exist?

2. If more than one such cycle exist then How one can print cycle with minimum weight among them??

Is it possible to solve these problem in linear time?? Please suggest me optimal solution for these problem...It will be much helpful if one can provide code also.

Problem Statement

A matrix consist of N rows and M column. Select exactly one element from each row such that sum of selected element is maximum possible and sum of column number from which these elements are selected is less than or equal to M. Output this maximum possible sum. Assume 0 based indexing. All elements in matrix is non negative integer less than 10^9.

Example

if N = 3 and M = 3, and matrix is 1 2 3 3 1 4 3 2 1 then output is 9. as we can select elements at (0, 1), (1, 2), (3, 0). sum of column number here is 1 + 2 + 0 = 3

My Approach

I tried to solve it in bottom up manner. I make a dp[n][m] where dp[i][j] represent maximum sum till ith row where sum of column number is j.but it takes me O(M) time to fill each cell in dp as i calculate sum for all possible ways to reach at that state and then select optimal.Thus overall complexity reach to O(N * N * M).

What i want?

I think there should be an approach that can solve this problem in less than O(N * M * M) complexity ? Please suggest any better approach