I have an algorithm which is meant to solve the following computational problem:

*Input: Sequence of positive integers*

*Output: A Sub-sequence of some desired length derived from original Sequence such that the sum of the sub-sequence’s elements are the minimum sum possible*

The Algorithm I have to solve this problem is implemented as a method in Java:

`public int[] runA(int k) { //k is desired length of sub-sequence /*Sequence S is the original sequence provided as input, it is available as a class variable for the class 'MinimumSubsequence' which this method 'runA' is apart of*/ //A is Sequence S copy with pseudo-boolean values attached to each element in S int[][] A = new int[this.S.length][2]; //B is size K array storing the k smallest elements found in S along with their indexes int[][] B = new int[k][2]; //initialization for (int i = 0; i < this.S.length; i++) { A[i][0] = this.S[i]; A[i][1] = False; } for (int i = 0; i < k; i++) { B[i][0] = this.S[i]; B[i][1] = i; } //Execution //search for k smallest elements in sequence S for (int i = 0; i < k; i++) { for (int j = 0; j < this.S.length; j++) { if (A[j][0] <= B[i][0] && A[j][1] == False) { B[i][0] = A[j][0]; B[i][1] = j; } A[(B[i][1])][1] = True; } } //build subsequence int[][] C = new int[this.S.length][2]; for (int i = 0; i < C.length; i++) { C[i][1] = False; } for (int i = 0; i < C.length; i++) { for (int j = 0; j < B.length; j++) { if (B[j][1] == i && (C[i][1] == False)) { C[i][0] = B[j][0]; C[i][1] = True; } } } int[] D = new int[k]; int j = 0; for (int i = 0; i < C.length; i++) { if (C[i][1] == True) { D[j] = C[i][0]; j++; } } return D; } `

The algorithm basically works by scanning the original sequence provided, each time scanning for the next smallest number. Once it has found the k smallest numbers in the sequence it builds and returns a sub-sequence made from those smallest elements in the original sequence

I believe that this algorithm does correctly solve the computational problem and that the running time of this algorithm is in O(N) (N being size of input sequence). I would just like some verification about the correctness and efficiency of this algorithm. I am also wondering if there exists are more efficient algorithm to solve this computational problem as I’m just not very satisfied with this one but can think of no other approach.