配列の最大差を求める - アルゴリズムの最適化ソリューション

Question

私はHackerRank - Max Differenceでalgoを解決することを実践しました。 D [0]、D [1]、...、D [N-1]：あなたは、n個の要素を持つ配列を指定されている

：

ここで与えられた問題です。隣接するすべてのサブアレイの最大差の合計（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つのテストケースを通過しましたが、タイムアウト（> = 2s）のために失敗したもう1つのテストケースを通過しませんでした。

「状態は次のとおりです：タイムアウトにより終了しました」

このコードをさらに最適化する方法を教えてください。

ありがとうございます！

Answer 1

既にPythonにanswerがありました。ここで私からのObjective Cのバージョンがあります：

@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のために失敗した：「ステータス：間違った答えを」。そのための修正を見つけることを願っています。

EDIT：

は、すべてのテストケースを渡さWORKINGコードを更新しました。前に間違ったデータ型が使用されました。