我在HackerRank - Max Difference上练习解决算法。
以下是问题描述:
给定一个包含n个元素的数组:d[0],d[1],...,d[n-1]。计算所有连续子数组的最大差异的总和(S)。
形式化:
S = sum{max{d[l,...,r]} - min{d[l, ..., r}},∀ 0 <= l <= r < n
输入格式:
n
d[0] d[1] ... d[n-1]
输出格式:
S
样例输入:
4
1 3 2 4
样例输出:
12
解释:
l = 0; r = 0;
array: [1]
sum = max([1]) - min([1]) = 0
l = 0; r = 1;
array: [1,3]
sum = max([1,3]) - min([1,3]) = 3 - 1 = 2
l = 0; r = 2;
array: [1,3,2]
sum = max([1,3,2]) - min([1,3,2]) = 3 - 1 = 2
l = 0;r = 3;
array: [1,3,2,4]
sum = max([1,3,2,4]) - min([1,3,2,4]) = 4 - 1 = 3
l = 1; r = 1 will result in zero
l = 1; r = 2;
array: [3,2]
sum = max([3,2]) - min([3,2]) = 3 - 2 = 1;
l = 1; r = 3;
array: [3,2,4]
sum = max ([3,2,4]) - min([3,2,4]) = 4 - 2 = 2;
l = 2; r = 2; will result in zero
l = 2; r = 3;
array:[2,4]
sum = max([2,4]) - min([2,4]) = 4 -2 = 2;
l = 3; r = 3 will result in zero;
Total sum = 12
这是我的解决方案:
-(NSNumber*)sum:(NSArray*) arr {
int diff = 0;
int curr_sum = diff;
int max_sum = curr_sum;
for(int i=0; i<arr.count; i++)
{
for(int j=i; j<=arr.count; j++) {
// Calculate current diff
if (!(j-i > 1)) {
continue;
}
NSArray *array = [arr subarrayWithRange:NSMakeRange(i, j-i)];
if (!array.count || array.count == 1) {
continue;
}
int xmax = -32000;
int xmin = 32000;
for (NSNumber *num in array) {
int x = num.intValue;
if (x < xmin) xmin = x;
if (x > xmax) xmax = x;
}
diff = xmax-xmin;
// Calculate current sum
if (curr_sum > 0)
curr_sum += diff;
else
curr_sum = diff;
// Update max sum, if needed
if (curr_sum > max_sum)
max_sum = curr_sum;
}
}
return @(max_sum);
}
一共有10个测试用例。
以上解决方案通过了前5个测试用例,但未能通过其他5个测试用例,这些测试用例因超时而失败(>=2s)。
"状态:由于超时而终止"。
请帮我进一步优化此代码。
谢谢!