数组中的Java递归差异

我目前正在学习Java，并且偶然发现我无法完成的练习。数组中的Java递归差异

任务是编写一个递归方法，该方法接受一个数组并返回最大值和最小值的差值。

例如{12, 5, 3, 8}应返回5（8 - 3）。请注意，只允许按正确顺序比较值（result = rightValue - leftValue）。例如12-3 = 9将不被允许。把它看作股票价值。你想知道哪个时间买卖股票赚取最大的利润。

这很容易实现迭代，但我不知道如何做递归。也是通过分治来解决问题的一部分。

来源

2016-05-16 Nbert.

告诉我们你到目前为止试过的东西 – attaboy182

@ Turing85不，只允许以正确的顺序比较值。把它看作股票价值。你想知道哪个时间买卖股票赚取最大的利润。 –

有太多可能的答案，或者对于这种格式，答案太长。请添加详细信息以缩小答案集或隔离几个段落中可以回答的问题。 +你的例子对我没有意义。 –

我用鸿沟和征服这里的做法。我相信这里的诀窍是在我们将主数组分割的两个数组中包含中间值。

/*这里被忽略的边缘情况*/

int findMax(int[] arr, int left, int right){ 

if(right-left == 1) return (arr[right]-arr[left]); 

int middle = left + (right-left)/2; 

int max1 = findMax(arr, left, middle); 
int max2 = findMax(arr, middle, right); 

if(max1 >= 0 && max2 >= 0) return max1+max2; 

else return Math.max(max1,max2); 

}

来源

2016-05-16 19:16:59 attaboy182

这解决了我的问题，非常感谢！ –

你能解释为什么中间必须是“左+（左 - 右）/ 2”吗？我预计它只是'（左 - 右）/ 2'。 –

-3

算法（这是相当多排序任务，则该减法步骤是微不足道的）

1）首先排序阵列（用于大阵列和较小的阵列递归插入递归归并排序）。

合并排序（https://en.wikipedia.org/wiki/Merge_sort）

插入排序（https://en.wikipedia.org/wiki/Insertion_sort）

2）使用阵列最小索引[0]以获得最小的值&指数[array.length-1]，以获得最大

3）计算出的差异（不知道你用正确的顺序是什么意思？）

来源

2016-05-16 18:47:37 cyber101

这将导致12-3 = 9，OP明确表示不是答案。 – mks

如果您对数组进行排序，那么您不必担心订单。我被具体要求实施分而治之算法。 –

我不得不承认，我没有很好地解释我的问题是什么。此任务旨在模拟股票市场。您试图通过以最低价格购买并以最高价格出售来最大化您的利润。 –

嗯，我不认为递归是在这个非常有效的。你可能永远不会这样做（除了家庭作业）。像这样的东西会做：

int findGreatestDifference(Vector<Integer> numbers, int greaterDifference){ 
    if(numbers.size() == 1) //return at last element 
     return greaterDifference; 
    int newDifference = (numbers.get(0) - numbers.get(1)); 
    if (newDifference > greaterDifference) 
     greaterDifference = newDifference; 

    numbers.remove(numbers.size() - 1); 
    findGreatestDifference(numbers, greaterDifference); 
    return greaterDifference; 
}

第一次调用它，传递0作为较大的差异，并再次我不觉得这是因为做到这一点的有效途径。迭代对此会更好。

我希望这会有所帮助。

来源

2016-05-16 19:29:56

我知道递归对于这个练习来说是愚蠢的，但是它的一部分是迭代的，另一部分是递归的。谢谢你的帮助！ –

数组中的Java递归差异

回答

相关问题