在阵列中找到最大差异-需要算法解决方案优化 [英] Find Max Difference in Array - Need Algorithm Solution Optimization
问题描述
我练习了在 HackerRank-最大差异上解决算法的问题.
I practised solving an algo on HackerRank - Max Difference.
这是给出的问题:
为您提供了一个包含n个元素的数组:d [0]，d [1]，...，d [n-1].计算所有连续子数组的最大差之和.
You are given an array with n elements: d[ 0 ], d[ 1 ], ..., d[n-1]. Calculate the sum(S) of all contiguous sub-array's max difference.
正式:
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)而失败.
There were totally 10 test cases. The above solution passed first 5 test cases, but didn't get passed through the other 5, which were failed due to time out (>=2s).
这里是状态:由于超时而终止."
"Here's the Status: Terminated due to timeout".
请帮助我进一步优化此代码.
Please help me on how this code can be further optimised.
谢谢！
推荐答案
Python中已经有一个 answer .这是我的Objective C版本:
Already there was an answer in Python. Here's the Objective C version from me:
@interface Stack : NSObject {
NSMutableArray* m_array;
int count;
}
- (void)push:(id)anObject;
- (id)pop;
- (id)prev_prev;
- (void)clear;
@property (nonatomic, readonly) NSMutableArray* m_array;
@property (nonatomic, readonly) int count;
@end
@implementation Stack
@synthesize m_array, count;
- (id)init
{
if( self=[super init] )
{
m_array = [[NSMutableArray alloc] init];
count = 0;
}
return self;
}
- (void)push:(id)anObject
{
[m_array addObject:anObject];
count = m_array.count;
}
- (id)pop
{
id obj = nil;
if(m_array.count > 0)
{
obj = [m_array lastObject];
[m_array removeLastObject];
count = m_array.count;
}
return obj;
}
- (id)prev_prev
{
id obj = nil;
if(m_array.count > 0)
{
obj = [m_array lastObject];
}
return obj;
}
- (void)clear
{
[m_array removeAllObjects];
count = 0;
}
@end
@interface SolutionClass:NSObject
/* method declaration */
-(NSNumber*)findDiff:(NSArray*) arr;
@end
@implementation SolutionClass
-(NSNumber*)findDiff:(NSArray*) arr {
NSNumber *maxims = [self sum:arr negative:NO];
NSNumber *minims = [self sum:arr negative:YES];
NSNumber *diff = @(maxims.longLongValue+minims.longLongValue);
NSLog(@"diff: %@", diff);
return diff;
}
-(NSNumber*)sum:(NSArray*) arr negative:(BOOL)negate {
Stack *stack = [Stack new];
[stack push:@{@(-1): [NSNull null]}];
long long sum = 0;
for(int i=0; i<arr.count; i++) {
NSNumber *num = arr[i];
if (negate) {
num = @(-num.longLongValue);
}
NSDictionary *prev = stack.m_array.lastObject;
NSNumber *prev_i = (NSNumber*)prev.allKeys[0];
NSNumber *prev_x = (NSNumber*)prev.allValues[0];
if ([self isNumber:prev_x]) {
while (num.longLongValue > prev_x.longLongValue) {
prev_i = (NSNumber*)prev.allKeys[0];
prev_x = (NSNumber*)prev.allValues[0];
prev = [stack pop];
NSDictionary *prev_prev_Dict = [stack prev_prev];
NSNumber *prev_prev_i = (NSNumber*)prev_prev_Dict.allKeys[0];
sum += prev_x.longLongValue * (i-prev_i.longLongValue) * (prev_i.longLongValue - prev_prev_i.longLongValue);
prev = stack.m_array.lastObject;
prev_x = (NSNumber*)prev.allValues[0];
if (![self isNumber:prev_x]) {
break;
}
}
}
[stack push:@{@(i): num}];
}
NSLog(@"Middle: sum: %lld", sum);
while (stack.count > 1) {
NSDictionary *prev = [stack pop];
NSDictionary *prev_prev_Dict = [stack prev_prev];
NSNumber *prev_i = (NSNumber*)prev.allKeys[0];
NSNumber *prev_x = (NSNumber*)prev.allValues[0];
NSNumber *prev_prev_i = (NSNumber*)prev_prev_Dict.allKeys[0];
sum += prev_x.longLongValue * (arr.count-prev_i.longLongValue) * (prev_i.longLongValue - prev_prev_i.longLongValue);
prev = stack.m_array.lastObject;
prev_x = (NSNumber*)prev.allValues[0];
if (![self isNumber:prev_x]) {
break;
}
}
NSLog(@"End: sum: %lld", sum);
return @(sum);
}
-(BOOL)isNumber:(id)obj {
if ([obj isKindOfClass:[NSNumber class]]) {
return 1;
}
return 0;
}
@end
以上解决方案适用于7个测试用例，但不适用于其他3个这样的用例:状态:错误答案".希望也能找到解决办法.
The above solution works well for 7 test cases, but fails for the other 3 saying this: "Status: Wrong Answer". Hoping to find a fix for that too.
已更新通过所有测试用例的 WORKING 代码.以前使用了错误的数据类型.
Have updated the WORKING code that passed all the test cases. Wrong data types were used before.
这篇关于在阵列中找到最大差异-需要算法解决方案优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
