jeudi 26 janvier 2017

function using unordered_map to determine subarray indices failing

I'm attempting to cout the elements of input array "arr" that was used to determine max sum of a subarray, hereinafter named "maxSum" (which is determined elsewhere, and confirmed to be correct). The function showSubArray() accepts as parameters the array arr, the length of the array n, and maxSum. Input array is positive and negative ints. Below is a set of test arrays with the result. Fail means that arr[0] is printed to the screen with a space separating them INFINITELY. I can't see any discernable pattern in the input that would cause this. Any help greatly appreciated and I am not beholden to the unordered_map approach. Getting the indices from the function that determined the maxSum is not an acceptable solution.

#include <unordered_map>
#include <iostream>
using std::cout;

int main() {

   //int arr[] = { 1, 4, -9, 8, 1, 3, 3, 1, -1, -4, -6, 2, 8, 19, -10, -11 };
   //   runs ok, inputs: n=16, maxSum = 34

   //int arr[] = { 2, 9, 8, 6, 5, -11, 9, -11, 7, 5, -1, -8, -3, 7, -2 };
   // ***fails, inputs: n=15, maxSum = 30

   //int arr[] = { 10, -11, -1, -9, 33, -45, 23, 24, -1, -7, -8, 19 };
   //    runs ok, n=12, maxSum = 50

   //int arr[] = { 31, -41, 59, 26, -53, 58, 97, -93, -23, 84 };
   //    runs ok n=10 maxSum = 187

   //int arr[] = { 3, 2, 1, 1, -8, 1, 1, 2, 3 };
   // ***fails, inputs: n=9 maxSum = 7

   int arr[] = { 12, 99, 99, -99, -27, 0, 0, 0, -3, 10 };
   // ***fails, n=10 maxSum = 210

   //int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
   //    runs ok, inputs: n=9 maxSum = 6

   showSubArray(arr, n, maxSum);
   return 0;
}


void showSubArray(int arr[], int n, int maxSum) {
    std::unordered_map<int, int> aMap;
    int accumulator = 0;

    for (int i = 0; i < n; i++) {
        accumulator += arr[i];

        if (accumulator == maxSum) {
            for(int j = 0; j <= i; i++) {
                cout << arr[j];
                cout << " ";
            }
            cout << '\n';
            return;
        }

        if (aMap.find(accumulator - maxSum) != aMap.end()) {
            for (int j = aMap[accumulator - maxSum] + 1; j <= i; j++) {
                cout << arr[j];
                cout << " ";
            }
            cout << '\n';
            return;
        }

        aMap[accumulator] = i;
    }

    cout << "Subarray not found!\n";
}

Aucun commentaire:

Enregistrer un commentaire