Maximum subarray

gistfile1.m

// interface
@interface MaxSubArray : NSObject

@end

// extension
@interface MaxSubArray()

@end

@implementation MaxSubArray
-(void) maxSubArrayFor:(NSArray*)array {
    NSInteger bestSumStartIndex = 0;
    NSInteger bestSumEndIndex = 0;
    NSInteger maxSum = 0;
    NSInteger currentIndex = -1;
    NSInteger currentSum = 0;
    for (int i=0; i<[array count]; i++) {
        NSInteger value = currentSum + [[array objectAtIndex:i]integerValue];
        if (value > 0) {
            if (currentSum == 0) {
                currentIndex = i;
            }
            currentSum = value;
        } else {
            currentSum = 0;
        }
        
        if (currentSum > maxSum) {
            maxSum = currentSum;
            bestSumStartIndex = currentIndex;
            bestSumEndIndex = i;
        }
    }
    NSLog(@"start %lu end %lu", bestSumStartIndex, bestSumEndIndex);
}
@end

MaxSubArray *subArray = [MaxSubArray new];
[subArray maxSubArrayFor:[NSArray arrayWithObjects:[NSNumber numberWithInteger:-1], [NSNumber numberWithInteger:1], [NSNumber numberWithInteger:3], [NSNumber numberWithInteger:1], [NSNumber numberWithInteger:-5], nil]];