C# 如何找到数组中的最大差异
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18956740/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to find the Largest Difference in an Array
提问by Randal Cunanan
Suppose I have an array of integers:
假设我有一个整数数组：
int[] A = { 10, 3, 6, 8, 9, 4, 3 };
My goal is to find the largest difference between A[Q] and A[P] such that Q > P.
我的目标是找到 A[Q] 和 A[P] 之间的最大差异，使得 Q > P。
For example, if P = 2 and Q = 3, then
例如，如果 P = 2 且 Q = 3，则
diff = A[Q] - A[P]
diff = 8 - 6
diff = 2
If P = 1 and Q = 4
如果 P = 1 且 Q = 4
diff = A[Q] - A[P]
diff = 9 - 3
diff = 6
Since 6 is the largest number between all the difference, that is the answer.
由于 6 是所有差异中最大的数字，这就是答案。
My solution is as follows (in C#) but it is inefficient.
我的解决方案如下（在 C# 中），但效率低下。
public int solution(int[] A) {
int N = A.Length;
if (N < 1) return 0;
int difference;
int largest = 0;
for (int p = 0; p < N; p++)
{
for (int q = p + 1; q < N; q++)
{
difference = A[q] - A[p];
if (difference > largest)
{
largest = difference;
}
}
}
return largest;
}
How can I improve this so it will run at O(N)? Thanks!
我该如何改进它才能让它以 O(N) 运行？谢谢！
Simply getting the max and min wont work. Minuend (Q) should come after the Subtrahend (P).
简单地获得最大值和最小值是行不通的。被减数 (Q) 应在减数 (P) 之后。
This question is based on the "Max-profit" problem in codility (http://codility.com/train/). My solution only scored 66%. It requires O(N) for a score of 100%.
这个问题基于 codility ( http://codility.com/train/) 中的“最大利润”问题。我的解决方案只得分 66%。它需要 O(N) 才能获得 100% 的分数。
采纳答案by Daniel Hilgarth
The following code runs in O(n) and shouldconform to the specification (preliminary tests on codility were successful):
以下代码在 O(n) 中运行并且应该符合规范（对编码的初步测试成功）：
public int solution(int[] A)
{
int N = A.Length;
if (N < 1) return 0;
int max = 0;
int result = 0;
for(int i = N-1; i >= 0; --i)
{
if(A[i] > max)
max = A[i];
var tmpResult = max - A[i];
if(tmpResult > result)
result = tmpResult;
}
return result;
}
Update:
I submitted it as solution and it scores 100%.
更新：
我将它作为解决方案提交，它的得分为 100%。
Update 02/26/16:
The original task description on codility stated that "each element of array A is an integer within the range [0..1,000,000,000]."
If negative values would have been allowed as well, the code above wouldn't return the correct value. This could be fixed easily by changing the declaration of maxto int max = int.MinValue;
2016 年 2
月 26 日更新：关于 codility 的原始任务描述指出“数组 A 的每个元素都是 [0..1,000,000,000] 范围内的整数。”
如果也允许负值，则上面的代码将不会返回正确的值。这可以通过将声明更改max为int max = int.MinValue;
回答by King King
After some attempts, I end up with this:
经过一些尝试，我最终得到了这个：
int iMax = N - 1;
int min = int.MaxValue, max = int.MinValue;
for (int i = 0; i < iMax; i++) {
if (min > A[i]) min = A[i];
if (max < A[N - i - 1]){
iMax = N - i - 1;
max = A[iMax];
}
}
int largestDiff = max - min;
NOTE: I have just tested it with some cases. Please if you find any case in which it doesn't work, let me know in the comment. I'll try to improve it or remove the answer. Thanks!
注意：我刚刚在某些情况下对其进行了测试。如果您发现任何不起作用的情况，请在评论中告诉我。我会尝试改进它或删除答案。谢谢！
回答by user2831284
int FirstIndex = -1;
int SecondIndex = -1;
int diff = 0;
for (int i = A.Length-1; i >=0; i--)
{
int FirstNo = A[i];
int tempDiff = 0;
for (int j = 0; j <i ; j++)
{
int SecondNo = A[j];
tempDiff = FirstNo - SecondNo;
if (tempDiff > diff)
{
diff = tempDiff;
FirstIndex = i;
SecondIndex = j;
}
}
}
MessageBox.Show("Diff: " + diff + " FirstIndex: " + (FirstIndex+1) + " SecondIndex: " + (SecondIndex+1));
回答by Alexander M.
PHP solution for MaxProfit of codility test task giving 100/100 found at http://www.rationalplanet.com/php-related/maxprofit-demo-task-at-codility-com.html
可在http://www.rationalplanet.com/php-related/maxprofit-demo-task-at-codility-com.html 上找到的 Codility 测试任务 MaxProfit 的 PHP 解决方案给出 100/100
function solution($A) {
$cnt = count($A);
if($cnt == 1 || $cnt == 0){
return 0;
}
$max_so_far = 0;
$max_ending_here = 0;
$min_price = $A[0];
for($i = 1; $i < $cnt; $i++){
$max_ending_here = max(0, $A[$i] - $min_price);
$min_price = min($min_price, $A[$i]);
$max_so_far = max($max_ending_here, $max_so_far);
}
return $max_so_far;
}
回答by Jung Oh
100% score JavaScript solution.
100% 得分 JavaScript 解决方案。
function solution(A) {
if (A.length < 2)
return 0;
// Init min price and max profit
var minPrice = A[0];
var maxProfit = 0;
for (var i = 1; i < A.length; i++) {
var profit = A[i] - minPrice;
maxProfit = Math.max(maxProfit, profit);
minPrice = Math.min(minPrice, A[i]);
}
return maxProfit;
}
回答by user3403187
Python solution
Python解决方案
def max_diff_two(arr):
#keep tab of current diff and min value
min_value = arr[0]
#begin with something
maximum = arr[1] - arr[0]
new_min = min_value
for i,value in enumerate(arr):
if i == 0:
continue
if value < min_value and value < new_min:
new_min = value
current_maximum = value - min_value
new_maximum = value - new_min
if new_maximum > current_maximum:
if new_maximum > maximum:
maximum = new_maximum
min = new_min
else:
if current_maximum > maximum:
maximum = current_maximum
return maximum
回答by craftsmannadeem
Here is the O(n) Java implementation
这是 O(n) Java 实现
public static int largestDifference(int[] data) {
int minElement=data[0], maxDifference=0;
for (int i = 1; i < data.length; i++) {
minElement = Math.min(minElement, data[i]);
maxDifference = Math.max(maxDifference, data[i] - minElement);
}
return maxDifference;
}
回答by stukennedy
100% for Javascript solution using a more elegant functional approach.
100% 使用更优雅的函数式方法的 Javascript 解决方案。
function solution(A) {
var result = A.reverse().reduce(function (prev, val) {
var max = (val > prev.max) ? val : prev.max
var diff = (max - val > prev.diff) ? max - val : prev.diff
return {max: max, diff: diff}
}, {max: 0, diff: 0})
return result.diff
}
回答by afrizaliman
PHP Solution
PHP解决方案
<?php
$a = [0,5,0,5,0];
$max_diff = -1;
$min_value = $a[0];
for($i = 0;$i<count($a)-1;$i++){
if($a[$i+1] > $a[$i]){
$diff = $a[$i+1] - $min_value;
if($diff > $max_diff){
$max_diff = $diff;
}
} else {
$min_value = $a[$i+1];
}
}
echo $max_diff;
?>
