# Minimum Subsequence Sum Algorithm Verification 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];         //B is size K array storing the k smallest elements found in S along with their indexes         int[][] B = new int[k];          //initialization         for (int i = 0; i < this.S.length; i++) {             A[i] = this.S[i];             A[i] = False;         }         for (int i = 0; i < k; i++) {             B[i] = this.S[i];             B[i] = 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] <= B[i] && A[j] == False) {                     B[i] = A[j];                     B[i] = j;                 }                 A[(B[i])] = True;             }         }          //build subsequence         int[][] C = new int[this.S.length];         for (int i = 0; i < C.length; i++) {             C[i] = False;         }         for (int i = 0; i < C.length; i++) {             for (int j = 0; j < B.length; j++) {                 if (B[j] == i && (C[i] == False)) {                     C[i] = B[j];                     C[i] = True;                 }             }         }         int[] D = new int[k];         int j = 0;         for (int i = 0; i < C.length; i++) {             if (C[i] == True) {                 D[j] = C[i];                 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. Posted on Categories proxies