我试图cout输入数组“arr”的元素,用于确定子阵列的最大总和,下文称为“maxSum”(在别处确定,并确认是正确的)。 函数showSubArray()接受数组arr,数组n的长度和maxSum作为参数。 输入数组是正负的整数。 下面是一组带有结果的测试数组。 失败意味着arr [0]被打印到屏幕上,并且空间将它们无限分开。 我无法在输入中看到任何可识别的模式。 任何帮助非常感谢,我不赞成unordered_map方法。 从确定maxSum的函数中获取索引不是可接受的解决方案。
#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; j++) { // ACB found error here ^ (I had it as "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"; }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; j++) { // ACB found error here ^ (I had it as "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"; }最满意答案
if (accumulator == maxSum) { for(int j = 0; j <= i; i++) {你在这里递增但是你想增加j因为0总是小于i> i> 0直到它溢出
if (accumulator == maxSum) { for(int j = 0; j <= i; i++) {you are incrementing i here but you want to increment j cause 0 will always be smaller i for i > 0 until it overflows
更多推荐
发布评论