Optimal algorithm to reorder two arrays putting the common elements first
Let's say we have two arrays having some elements in common (the arrays can't contain duplicates)
Array 1 = [A, K, C, F]
Array 2 = [B, D, C, K]
I would like to reorder the two arrays with the following requirements:
 The common elements must be at the beginning of the arrays (without any specific order)
 The common elements in the two arrays must be exactly at the same positions
 The noncommon elements can be in any position (after the common ones)
 Swapping two elements which are farther away costs more than swapping two elements which are closed together (we can assume a linear cost function where
cost of swapping elements at indexes i and j = abs(i  j)
)
For the example above having [C, K]
in common, we could produce the following valid rearrangement:
Array 1 = [C, K, A, F]
Array 2 = [C, K, B, D]
Another valid rearrangement could be:
Array 1 = [K, C, A, F]
Array 2 = [K, C, B, D]
Although it is quite trivial to write a basic algorithm that swaps the two input arrays to generate a valid output, it is not clear to me how to write the "optimal" (in sense of minimal costs) one.
I am not even sure if this algorithm could be solved using dynamic programming or similar techniques. Has anyone already seen this problem somewhere before or has an idea on how to solve it?
1 answer

I will describe my ideas, sorry for my english:
First, find out which are the common elements.
Second, go through both list, at the same time, from the left to the right. There might be three cases:
a) there are no common elements in the position. You go to the next position.
b) there is one common element in the position. Then you swap the common element and its complement to the most left position not occupied by common elements.
c) there are two common elements in the position. Then you swap the one to the most left position not occupied by common elements or the next position to the right and add the complements. If this position is also occupied by one or two common elements, you keep these in a store and try to empty this store while moving on. Realize that this store can grow larger than one or two elements.
By this you should be able to extract where to move which element, with an optimal solution with respect to your requirements.
remark: This seems quite logic to me now but it would be nice to know how it worked ;)
See also questions close to this topic

Array Manipulation : HackerRank Questions : JAVA
I am doing this Array Manipulation problem from hackerrank and it tells me compile error is Terminated due to timeout.
For small arrays my method work perfectly. This error only happens for bigger array values.
Here is the question link. Question Here
Starting with a 1indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in your array.
For example, the length of your array of zeros . Your list of queries is as follows:
a b k 1 5 3 4 8 7 6 9 1
Add the values of between the indices and inclusive:
index > 1 2 3 4 5 6 7 8 9 10 [0,0,0, 0, 0,0,0,0,0, 0] [3,3,3, 3, 3,0,0,0,0, 0] [3,3,3,10,10,7,7,7,0, 0] [3,3,3,10,10,8,8,8,1, 0]
The largest value is after all operations are performed.
Given below is my method.
static long arrayManipulation(int n, int[][] queries) { long max = 0L; long[] arr = new long[n]; for (int i = 0; i < n; i++) { arr[i] = 0L; } for (int i = 0; i < queries.length; i++) { int[] q = queries[i]; int start = q[0]  1; int end = q[1]  1; int val = q[2]; long tempMax = updateVal(start, end, val, arr); if (tempMax > max) { max = tempMax; } } return max; } static long updateVal(int start, int end, int val, long[] arr) { long max = 0L; for (int i = start; i <= end; i++) { arr[i] = arr[i] + val; if (arr[i] > max) { max = arr[i]; } } return max; }
Given below are few test classes that doesn't work with my code.
Test1 Test2 Test3Please help me to figure this out. I searched for lots of answers based on java.
But I couldn't understand them.
This is my last resort. Please help. 
How would you go about coding this java program with and array and methods?
In
main()
, generate two random int values: one for the number of rows, another for the number of columns. Limit the number of rows and columns so they fall between 1 and 10, inclusive.Pass the rows and columns as arguments to a void method. Use the row and column parameters to construct a twodimensional array. Then, populate the array with random values of either a 0 or a 1 using appropriate loops and the Random class method of generating random numbers.
Example:
 The
main()
method generates 3 and 6
 The
 3 and 6 are passed to the void method
 The void builds a 3 row, 6 column array and populates it with random 0s and 1s. Example:
0 0 1 0 1 1
1 1 0 0 0 0
1 0 0 0 1 0
 Finally, pass the array to a valuereturning method. Display the count of 0s and 1s in each row within the method, like this (based on the data from the above run). Then, return the total number of zeros to main, and display that number in main.
Row 1: 3 zeros, 3 ones
Row 2: 2 zeros, 4 ones
Row 3: 4 zeros, 2 ones
Main should then display:
9 zeros

Functions contains (item,list,cb)
So I am supposed to write how this function is supposed to return a cb for true if the item is in the array. I wrote the following but I checked on MDN and it's wrong. It def looks wrong to me but I know I supposed to include return cb() to the equation. What am I doing wrong?
if(===item){ return cb(true) } else { return cb(false) } // contains checks if an item is present inside of the given array/list. function contains(item, list, cb) { // Pass true to the callback if it is, otherwise pass false.
I am getting an Unexpected token error in the MDN.

Procedural algorithm to determine which math operation should be performed last
I'm building a procedural algorithm to determine which operation to perform last in a mathematical formula.
For context, I have written a token parser and a small interpreter, using VBA for Microsoft Excel.
But this is a generic algorithm question, so I'm happy to communicate in whichever language you prefer.For the purposes of this algorithm, my interpreter only needs to support parentheses, multiplication and division. (Let's not complicate things with too many operators for the timebeing.)
My token parser is already working, so we have an array of token objects to work with.
Therefore, we can pass an array of token objects as input to the interpreter, and the interpreter should be able to determine which operations are being performed, simplify the expression, reduce the fraction, etc.
For example, if we pass this array of tokens:x*y/x*z
... ultimately my interpreter would be able to reduce the fraction toy/z
since the x's cancel out, and since multiplication takes precedence over division.However, I need to support parentheses to make this practical for a specific enduser application.
Things get complicated when you include parentheses ...
For example:a/(b*c/(d*e/f)*g/h)/i*(j/k)
what a mess! XDRecursion to the rescue!
We can greatly simplify this problem by splitting it into smaller problems.
Since multiplication takes precedence, we can split this into two sections:
a/(b*c/(d*e/f)*g/h)
/i*(j/k)
... and then recursively invoke my interpreter (function) on each of those two sections individually, which would then break them down into even smaller sections, until eventually the problem is simple enough to compute with ease. (Base case = no division operators left)My interpreter is mostly complete, the only thing that is missing is the ability to determine where to split the array of tokens.
In other words, I need to build an algorithm that can look at the placement of operators and parentheses, and figure out which operation occurs last, so I can split the token array in half.Given a sequential array of token objects, I have written some helper functions to produce sequential arrays of integers, representing the indexes of parentheses, multiplication operators, and division operators.
Dim tokenCount As Long 'Total number of tokens in the current input array Dim openParenIndexes() As Long 'Arrays of integers, representing token positions Dim closeParenIndexes() As Long Dim multiplicationIndexes() As Long Dim divisionIndexes() As Long
In the above example (using zerobased indexing):
openParenIndexes
=[2, 7, 22]
closeParenIndexes
=[13, 18, 26]
multiplicationIndexes
=[4, 9, 14, 21]
divisionIndexes
=[1, 6, 11, 16, 19, 24]
Again, these arrays are already populated and ready to use.
My program needs to be able to look at the information in these arrays, and figure out that the division operator at index19
is the final operator to be computed, and therefore the array of tokens should be split at that index.Using this information, what's the best way to begin creating this algorithm?
Should this also be a recursive algorithm?I presume more recursion could possibly make this easier, but I'm having trouble figuring out where to start.

Implementing FloydWarshall in Java
I'm trying to implement the FloydWarshall algorithm and I'm a bit stuck on how to go about it.
I'm taking in an unspecified amount of weighted edges, the input is 3 integers: the source, destination and weight. Example:
1 9 4
1 is source node, 9 is destination node and 4 is weight.
Here is my code below:
import java.util.*; public class FloydWarshall { public static void main(String[] args) { Scanner stdin = new Scanner(System.in); ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); ArrayList<Edge> edges = new ArrayList<Edge>(); while(stdin.hasNext()) { String[] str = stdin.nextLine().split("[\\s,]+"); ArrayList<Integer> inner = new ArrayList<Integer>(); for(int i = 0; i < str.length; i++) { inner.add(Integer.parseInt(str[i])); } list.add(inner); } Graph graph = new Graph(edges.size()); for(int i = 0; i < list.size(); i++) { graph.addEdge(edges, list.get(i).get(0), list.get(i).get(1), list.get(i).get(2)); } } } class Edge { int source; int destination; int weight; public Edge(int source, int destination, int weight) { this.source = source; this.destination = destination; this.weight = weight; } } class Graph { int vertices; int adjMatrix[][]; public Graph(int vertices) { this.vertices = vertices; this.adjMatrix = new int[vertices][vertices]; } public void addEdge(ArrayList<Edge> edges, int source, int destination, int weight) { Edge edge = new Edge(source, destination, weight); edges.add(edge); adjMatrix[source][destination] = weight; } }
I'm trying to implement an adjacency matrix for the FloydWarshall algorithm but I'm having trouble implementing it, I've never used an adjacency matrix so any help would be appreciated!

How should i guarantee consistency in database involving finance transaction operations
I am trying to figure out how to handle consistency in the database. In scenario:
User A has an accounting document in the database include a balance field representing the amount of his current money. (supposed initially he has 100$)
My system has many methods to charge his account.
 Suppose 2 methods occur at the same time, each method charges him for 10$, these steps occur concurrently in below orders:
 Method 1 READ his balance and store in memory (100$)
 Method 2 READ his balance and store in memory (100$) ... some business logics
 Method 1 UPDATE his balance by subtracting variable in memory by 10 (100$  10$) and then save it
 Method 2 UPDATE his balance by subtracting variable in memory by 10 (100$  10$) and then save it
This means he has been charged only 10$ instead of 20$.
I searched this situation a while and can not get it clear (sorry for my stupidity). Really appreciate yours helps to enlighten my featherbrained. :)

Parameters for Least Squares program not changing
I am trying to create a program that can approximate the parameters for a exponential function of the form
y = ae^bx
, that fits any given data set, I looked up and tried to understand and use the MarquardtLevenberg Algorithm, although in my implementation, the parameters at each iteration don't seem to be changing. Can anyone help point out what is wrong with my implementation, or do I simply not fully understand the algorithm?public class regression { boolean exponential; matrix data, estimate, gradient, hessian, diagHessian; double scalar; public regression(boolean exponential, double[][] data) { this.exponential = exponential; this.data = new matrix(data.length, data[0].length); this.data.copy(data); } public void approximate() { this.findDerivative(this.exponential); for (int i = 0; i < 10000; i++) { double s = this.evaluateError(); double x = this.currentError(); //if new error is smaller than old error if (s < x) { this.estimate = this.evaluate(); reload(); this.scalar = this.scalar / 10; } else { this.scalar = this.scalar * 10.0; } } } public matrix evaluate() { matrix a = new matrix(2, 2); matrix b = new matrix(2, 2); b = this.diagHessian; b.times(this.scalar); a = this.hessian.subtract(b); matrix r = a.inverse(); matrix x = this.gradient; matrix d = r.multiply(x); matrix y = this.estimate.subtract(d); return y; } public double currentError() { double error = 0.0; double w = this.estimate.arrayM[0][0]; double z = this.estimate.arrayM[1][0]; for (int i = 0; i < this.data.size; i++) { error += (this.data.arrayM[i][1]  (w * java.lang.Math.exp(z * this.data.arrayM[i][0]))) * (this.data.arrayM[i] [1]  (w * java.lang.Math.exp(z * this.data.arrayM[i][0]))); } return error * 0.5; } //evaluate the estimate matrix at the next iteration and //return a new matrix not effecting the current iteration public double evaluateError() { matrix a = new matrix(2, 2); matrix b = new matrix(2, 2); b = this.diagHessian; b.times(this.scalar); a = this.hessian.subtract(b); matrix r = a.inverse(); matrix x = this.gradient; matrix d = r.multiply(x); matrix y = this.estimate.subtract(d); double error = 0.0; double w = y.arrayM[0][0]; double z = y.arrayM[1][0]; for (int i = 0; i < this.data.size; i++) { error += (this.data.arrayM[i][1]  (w * java.lang.Math.exp(z * this.data.arrayM[i][0]))) * (this.data.arrayM[i] [1]  (w * java.lang.Math.exp(z * this.data.arrayM[i][0]))); } return error * 0.5; } public static matrix transpose(matrix b) { matrix a = new matrix(b.sizeX, b.size); for (int i = 0; i < b.size; i++) { for (int y = 0; y < b.sizeX; y++) { a.arrayM[y][i] = b.arrayM[i][y]; } } return a; } public void reload() { this.calcGradient(); this.calcHessian(); this.calcDiag(); } public void findDerivative(boolean expo) { if (expo) { //create estimate this.estimate = new matrix(2, 1); double a = 40000; double b = 0.00012; this.estimate.arrayM[0][0] = a; this.estimate.arrayM[1][0] = b; this.gradient = new matrix(2, 1); this.calcGradient(); this.hessian = new matrix(2, 2); this.calcHessian(); this.diagHessian = new matrix(2, 2); this.calcDiag(); this.scalar = 0.5; } } public void calcDiag() { for (int i = 0; i < this.hessian.size; i++) { this.diagHessian.arrayM[i][i] = 1.0; } } public void calcGradient() { if (this.exponential) { double a = this.estimate.arrayM[0][0]; double b = this.estimate.arrayM[1][0]; double s = 0.0; for (int i = 0; i < this.data.size; i++) { s += (this.data.arrayM[i][1]  a * java.lang.Math.exp(b * data.arrayM[i][0])) * (java.lang.Math.exp(b * data.arrayM[i][0])); } this.gradient.arrayM[0][0] = s; s = 0.0; for (int i = 0; i < this.data.size; i++) { s += (this.data.arrayM[i][1]  a * java.lang.Math.exp(b * data.arrayM[i][0])) * (this.data.arrayM[i][0] * a * java.lang.Math.exp(b * data.arrayM[i][0])); } this.gradient.arrayM[1][0] = s; } } public void calcHessian() { if (this.exponential) { double a = this.estimate.arrayM[0][0]; double b = this.estimate.arrayM[1][0]; double s = 0.0; matrix jacobian = new matrix(this.data.size, 2); for (int i = 0; i < jacobian.size; i++) { jacobian.arrayM[i][0] = Math.exp(b * this.data.arrayM[i][0]); jacobian.arrayM[i][1] = a * this.data.arrayM[i[0] * Math.exp(b * this.data.arrayM[i][0]); } matrix c = transpose(jacobian); matrix d = c.multiply(jacobian); this.hessian = d; } } }

How to pass an array of input parameters in scipy.optimize.minimize?
I want to use scipy.optimize.minimize to solve for a set of parameters by minimizing an error function.
The function called "error" returns the squared error for the function that I am trying to find z1,z2,z3(the parameters) for.
I have an array of x(called "b" in the function) and y(called "real" in the function) values.
The code below works fine if I set x and y to some integer, but not if I try to pass in an array of x and y values, to act as the variable "b" and "real" in the equation to be minimized.
Trying to pass in an array of X and Y values results in the error pasted below.
Is there a way to pass in arrays to act as a variable in an equation for the minimize function, instead of just a single integer?
Here is what my code looks like:
import numpy as np import pandas as pd from scipy.optimize import minimize #dataset file, with a column named x,y with 1000 rows f = pd.read_csv('Test_Data_.txt', sep='\t') #initial guess x0 = [1, 2, 3] #f['x'] and f['y'] are columns with 1000 rows #x = f['x'].values #y = f['y'].values x = 1 #these parameters work fine y = 4 #a function called inside the function to be minimized def est(z1, z2, z3, b): return z1 * b**2 + z2 * b + z3 #function to minimize def error(x, real, b): return (real  est(x[0], x[1], x[2], b))**2 print(minimize(error, x0, args = ( x, y), method='BFGS', tol=1e6))
Feeding in the array of x and y values produces the error:
Traceback (most recent call last): File "problem1.py", line 24, in <module> minimize(error, x0, args = ( np.array(list(f['y'].values)), np.array(list(f['x'].values))), method='BFGS', tol=1e6) File "/usr/local/lib/python3.5/distpackages/scipy/optimize/_minimize.py", line 595, in minimize return _minimize_bfgs(fun, x0, args, jac, callback, **options) File "/usr/local/lib/python3.5/distpackages/scipy/optimize/optimize.py", line 970, in _minimize_bfgs gfk = myfprime(x0) File "/usr/local/lib/python3.5/distpackages/scipy/optimize/optimize.py", line 300, in function_wrapper return function(*(wrapper_args + args)) File "/usr/local/lib/python3.5/distpackages/scipy/optimize/optimize.py", line 730, in approx_fprime return _approx_fprime_helper(xk, f, epsilon, args=args) File "/usr/local/lib/python3.5/distpackages/scipy/optimize/optimize.py", line 670, in _approx_fprime_helper grad[k] = (f(*((xk + d,) + args))  f0) / d[k] ValueError: setting an array element with a sequence.

How to speed up nsolve or the bisection method?
I am writing a program that requires a root finder of some sort, but every root finder I have used is unsatisfactorily slow. I'm looking for a way to speed this up.
I have used the SymPy's nsolve, and although this produces very precise results, it is very slow (if I do 12 iterations of my program it takes 12+ hours to run). I wrote my own bisection method, and this works much better, but is still very slow (12 iterations takes ~ 1 hour to run). I have been unable to find a symengine solver, or that is what I would be using. I will post both of my programs (with the bisection method and with nsolve). Any advice on how to speed this up is greatly appreciated.
Here is the code using nsolve:
from symengine import * import sympy from sympy import Matrix from sympy import nsolve trial = Matrix() r, E1, E = symbols('r, E1, E') H11, H22, H12, H21 = symbols("H11, H22, H12, H21") S11, S22, S12, S21 = symbols("S11, S22, S12, S21") low = 0 high = oo integrate = lambda *args: sympy.N(sympy.integrate(*args)) quadratic_expression = (H11E1*S11)*(H22E1*S22)(H12E1*S12)*(H21E1*S21) general_solution = sympify(sympy.solve(quadratic_expression, E1)[0]) def solve_quadratic(**kwargs): return general_solution.subs(kwargs) def H(fun): return fun.diff(r, 2)/2  fun.diff(r)/r  fun/r psi0 = exp(3*r/2) trial = trial.row_insert(0, Matrix([psi0])) I1 = integrate(4*pi*(r**2)*psi0*H(psi0), (r, low, high)) I2 = integrate(4*pi*(r**2)*psi0**2, (r, low, high)) E0 = I1/I2 print(E0) for x in range(10): f1 = psi0 f2 = r * (H(psi0)E0*psi0) Hf1 = H(f1).simplify() Hf2 = H(f2).simplify() H11 = integrate(4*pi*(r**2)*f1*Hf1, (r, low, high)) H12 = integrate(4*pi*(r**2)*f1*Hf2, (r, low, high)) H21 = integrate(4*pi*(r**2)*f2*Hf1, (r, low, high)) H22 = integrate(4*pi*(r**2)*f2*Hf2, (r, low, high)) S11 = integrate(4*pi*(r**2)*f1**2, (r, low, high)) S12 = integrate(4*pi*(r**2)*f1*f2, (r, low, high)) S21 = S12 S22 = integrate(4*pi*(r**2)*f2**2, (r, low, high)) E0 = solve_quadratic( H11=H11, H22=H22, H12=H12, H21=H21, S11=S11, S22=S22, S12=S12, S21=S21, ) print(E0) C = (H11  E0*S11)/(H12  E0*S12) psi0 = (f1 + C*f2).simplify() trial = trial.row_insert(x+1, Matrix([[psi0]])) # Free ICI Part h = zeros(x+2, x+2) HS = zeros(x+2, 1) S = zeros(x+2, x+2) for s in range(x+2): HS[s] = H(trial[s]).simplify() for i in range(x+2): for j in range(x+2): h[i, j] = integrate(4*pi*(r**2)*trial[i]*HS[j], (r, low, high)) for i in range(x+2): for j in range(x+2): S[i, j] = integrate(4*pi*(r**2)*trial[i]*trial[j], (r, low, high)) m = h  E*S eqn = m.det() roots = nsolve(eqn, float(E0)) print(roots)
Here is the code using my bisection method:
from symengine import * import sympy from sympy import Matrix from sympy import nsolve trial = Matrix() r, E1, E = symbols('r, E1, E') H11, H22, H12, H21 = symbols("H11, H22, H12, H21") S11, S22, S12, S21 = symbols("S11, S22, S12, S21") low = 0 high = oo integrate = lambda *args: sympy.N(sympy.integrate(*args)) quadratic_expression = (H11E1*S11)*(H22E1*S22)(H12E1*S12)*(H21E1*S21) general_solution = sympify(sympy.solve(quadratic_expression, E1)[0]) def solve_quadratic(**kwargs): return general_solution.subs(kwargs) def bisection(fun, a, b, tol): NMax = 100000 f = Lambdify(E, fun) FA = f(a) for n in range(NMax): p = (b+a)/2 FP = f(p) if FP == 0 or abs(ba)/2 < tol: return p if FA*FP > 0: a = p FA = FP else: b = p print("Failed to converge to desired tolerance") def H(fun): return fun.diff(r, 2)/2  fun.diff(r)/r  fun/r psi0 = exp(3*r/2) trial = trial.row_insert(0, Matrix([psi0])) I1 = integrate(4*pi*(r**2)*psi0*H(psi0), (r, low, high)) I2 = integrate(4*pi*(r**2)*psi0**2, (r, low, high)) E0 = I1/I2 print(E0) for x in range(11): f1 = psi0 f2 = r * (H(psi0)E0*psi0) Hf1 = H(f1).simplify() Hf2 = H(f2).simplify() H11 = integrate(4*pi*(r**2)*f1*Hf1, (r, low, high)) H12 = integrate(4*pi*(r**2)*f1*Hf2, (r, low, high)) H21 = integrate(4*pi*(r**2)*f2*Hf1, (r, low, high)) H22 = integrate(4*pi*(r**2)*f2*Hf2, (r, low, high)) S11 = integrate(4*pi*(r**2)*f1**2, (r, low, high)) S12 = integrate(4*pi*(r**2)*f1*f2, (r, low, high)) S21 = S12 S22 = integrate(4*pi*(r**2)*f2**2, (r, low, high)) E0 = solve_quadratic( H11=H11, H22=H22, H12=H12, H21=H21, S11=S11, S22=S22, S12=S12, S21=S21, ) print(E0) C = (H11  E0*S11)/(H12  E0*S12) psi0 = (f1 + C*f2).simplify() trial = trial.row_insert(x+1, Matrix([[psi0]])) # Free ICI Part h = zeros(x+2, x+2) HS = zeros(x+2, 1) S = zeros(x+2, x+2) for s in range(x+2): HS[s] = H(trial[s]).simplify() for i in range(x+2): for j in range(x+2): h[i, j] = integrate(4*pi*(r**2)*trial[i]*HS[j], (r, low, high)) for i in range(x+2): for j in range(x+2): S[i, j] = integrate(4*pi*(r**2)*trial[i]*trial[j], (r, low, high)) m = h  E*S eqn = m.det() roots = bisection(eqn, E0  1, E0, 10**(15)) print(roots)
As I said, they both work as they are supposed to, but they do so very slowly.

Maximum sum of elements in each interval
Given n  array of size , k  size of interval x  amount of elements to pick
1<=n<=5000, 1<=x<=n, 1<=k<=n
Problem is to find maximum sum of x elements such that there is at least one element in every interval of size k. Intervals are overlapping.
For n=4, k=2, x=2. Array [1,2,3,4] has 3 intervals of size 2, that is [1,2],[2,3],[3,4], then to cover those intervals with 2 elements we have 2 possibilities (1,3) or (2,4) and second one gives max sum so it is answer. We can't pick (3,4) becouse then there is no element picked in interval [1,2]
[19, 1, 22, 10, 1, 5, 50, 8, 10, 99, 100] n = 11, k = 3, x = 4
answer is 181 becouse we pick 22, 10, 50, 99 we can't pick 100 instead of 99 becouse then distance between 50 and 100 is more then k
there is 9 intervals in example [19, 1, 22],[1, 22, 10],[22, 10, 1]... and in each we need at least one choosen
public static long find(int[] arr, int k, int x) { Map<Integer, Map<Integer, long>> cache = new HashMap<>(); long maxSum = 0; for (int i = k1; i >= 0; i) { long sum = findTakeFirst(arr, k, x, i, cache); if (sum > maxSum) maxSum = sum; } return maxSum; } private static long findTakeFirst(int[] arr, int k, int x, int firstIdx, Map<Integer, Map<Integer, long>> cache) { if (x == 0)return 0; if (firstIdx + x > arr.length)return 0; if (x*k+firstIdx < arr.length)return 0; Map<Integer, long> map = cache.get(firstIdx); long cachedResult; if (map != null && (cachedResult = map.get(x)) != null) return cachedResult; long maxRemainSum = 0; for (int i = firstIdx + k; i >= firstIdx + 1; i) { if(firstIdx + k < arr.length1){ if(i != firstIdx + k && arr[i] < arr[firstIdx + k]) continue; } long remainSum = findTakeFirst(arr, k, x  1, i, cache); if (remainSum > maxRemainSum) maxRemainSum = remainSum; } if ((map = cache.get(firstIdx)) == null) cache.put(firstIdx, map = new HashMap<>()); long maxSum = arr[firstIdx] + maxRemainSum; map.put(x, maxSum); return maxSum; }
I've solved it with complexity O(nkx) and it gives correct answer but it's to slow and I need at least O(n*log(k)*x)

Minimal coin change(limited supply) with better time complexity discussion
The problem wants user to return a list of minimal coins as a change. For example , [.01, .10, .25] , .40 . And (all coins have 10 number of suppplies) should return [.10, .10, .10,.10] but not [.25,.1,.01,.01,.01,.01,.01]
The greedy approach doesn't work. This problem is Dynamic Programming problem. The described solution is O(2^n). How can we optimize it to O(n^2) or better with bottom up approach?
class CoinChange { public static List<Double> findMinRefundCombination(List<Double> inputCoins, double refundToMake) { List<Double> minCoins = new ArrayList<>(); List<Double> coinsAccumulatedSoFar = new ArrayList<>(); double refundSoFar = 0.0d; findMinRefundCombinationHelper(inputCoins, refundToMake, minCoins,coinsAccumulatedSoFar, 0, refundSoFar); System.out.println(minCoins.size()); return minCoins; } public static void findMinRefundCombinationHelper(List<Double> inputCoins, double refundToMake, List<Double> minCoins, List<Double> coinsAccumulatedSoFar, int curIndex, double refundSoFar) { if(refundSoFar > refundToMake  curIndex == inputCoins.size()) { return; } if(refundSoFar == refundToMake) { if(minCoins.isEmpty()) { for(Double coin: coinsAccumulatedSoFar) minCoins.add(coin); } else { if(coinsAccumulatedSoFar.size() < minCoins.size()) { minCoins.clear(); for(Double coin: coinsAccumulatedSoFar) minCoins.add(coin); } } } coinsAccumulatedSoFar.add(inputCoins.get(curIndex)); // findMinRefundCombinationHelper(inputCoins, refundToMake, minCoins, coinsAccumulatedSoFar,curIndex,refundSoFar + inputCoins.get(curIndex)); findMinRefundCombinationHelper(inputCoins, refundToMake, minCoins, coinsAccumulatedSoFar, curIndex + 1, refundSoFar + inputCoins.get(curIndex)); coinsAccumulatedSoFar.remove(coinsAccumulatedSoFar.size()  1); findMinRefundCombinationHelper(inputCoins, refundToMake, minCoins, coinsAccumulatedSoFar, curIndex + 1, refundSoFar); } public static void main(String[] args) { List<Double> inputCoins = new ArrayList<>(); inputCoins.add(.01); // inputCoins.add(); inputCoins.add(.10); inputCoins.add(.25); inputCoins.add(0.50); inputCoins.add(1.0); double refundToMake = 0.40; List<Double> minCoins = findMinRefundCombination(inputCoins, refundToMake); for(Double coin: minCoins) System.out.print(coin + " "); System.out.println(); } }

Maximum sum of elements in each interval
Array of size n, size of interval k and x amount of wanted elements. Problem is to find maximum sum of x elements such that there is at least one element in such interval, so there needs to be at least one in each window of size k. Intervals are overlapping.
1<=n<=5000, 1<=x<=n, 1<=k<=n
For n=4, k=2, x=2.
Array [1,2,3,4] has 3 intervals of size 2, that is [1,2],[2,3],[3,4], then to cover those intervals with 2 elements we have 2 possibilities (1,3) or (2,4) and second one gives max sum so it is answer. We can't pick (3,4) becouse then there is no element picked in interval [1,2]
I've solved it with complexity O(nkx) but it's to slow and I need at least O(n*log(k)*x)
[19, 1, 22, 10, 1, 5, 50, 8, 10, 99, 100] n = 11, k = 3, x = 4
answer is 181 becouse we pick 22, 10, 50, 99 we can't pick 100 instead of 99 becouse then distance between 50 and 100 is more then k
there is 9 intervals in example [19, 1, 22],[1, 22, 10],[22, 10, 1]... and in each we need at least one choosen