配列のiからjまでの合計値が最大となるところを求めるiPhoneアプリのサンプルコードを描いてみます。
動かすとこんな感じ
サンプルコード
#import “ViewController.h”
@interface ViewController ()
@property int showCounter;
@property (nonatomic, strong) NSArray *targets;
@end
@implementation ViewController
– (void)viewDidLoad
{
[super viewDidLoad];
NSArray *arr = @[@(13), @(–3), @(–25), @(20), @(–3), @(–16), @(–23), @(18), @(20), @(–7), @(12), @(–5)];
[self showNumbers:arr];
self.targets = arr;
UIButton *start = [UIButton buttonWithType:UIButtonTypeSystem];
[start setTitle:@”Maximum subarray” forState:UIControlStateNormal];
[start addTarget:self action:@selector(start) forControlEvents:UIControlEventTouchUpInside];
[start sizeToFit];
start.center = CGPointMake(160, 480);
[self.view addSubview:start];
}
– (void)start
{
int high = (int)self.targets.count – 1;
[self findMaximumSubarray:self.targets low:0 high:high];
}
– (void)showNumbers:(NSArray*)numbers
{
for (int i=0; i<numbers.count; i++) {
float x = i * 25 + 10;
UILabel *l = [[UILabel alloc] initWithFrame:CGRectMake(x, 50, 25, 20)];
l.textAlignment = NSTextAlignmentCenter;
l.font = [UIFont systemFontOfSize:12];
l.text = [numbers[i] stringValue];
l.backgroundColor = [UIColor orangeColor];
[self.view addSubview:l];
}
}
– (void)showSubarrayMax:(NSArray*)numbers Low:(int)low high:(int)high start:(int)start end:(int)end y:(float)y
{
for (int i=start; i<=end; i++) {
float x = i * 25 + 10;
UILabel *l = [[UILabel alloc] initWithFrame:CGRectMake(x, y, 25, 20)];
l.textAlignment = NSTextAlignmentCenter;
l.font = [UIFont systemFontOfSize:12];
l.text = [numbers[i] stringValue];
if (i >= low && i <= high) {
l.backgroundColor = [UIColor orangeColor];
} else {
l.backgroundColor = [UIColor lightGrayColor];
}
[self.view addSubview:l];
}
}
– (NSArray *)findMaxCrossingSubarray:(NSArray *)arr low:(int)low mid:(int)mid high:(int)high
{
int maxLeft = 0;
int leftSum = –HUGE_VAL;
int sum = 0;
for (int i=mid; i>=low; i–) {
sum = sum + [arr[i] intValue];
if (sum > leftSum) {
leftSum = sum;
maxLeft = i;
}
}
int maxRight = 0;
int rightSum = –HUGE_VAL;
sum = 0;
for (int j=mid+1; j<=high; j++) {
sum = sum + [arr[j] intValue];
if (sum > rightSum) {
rightSum = sum;
maxRight = j;
}
}
NSArray *result = @[@(maxLeft), @(maxRight), @(leftSum+rightSum)];
return result;
}
– (NSArray *)findMaximumSubarray:(NSArray *)arr low:(int)low high:(int)high
{
if (high == low)
{
return @[@(low),@(high), arr[low]];
}
else
{
int mid = (low + high) / 2.0;
NSArray *left = [self findMaximumSubarray:arr low:low high:mid];
NSArray *right = [self findMaximumSubarray:arr low:mid + 1 high:high];
NSArray *cross = [self findMaxCrossingSubarray:arr low:low mid:mid high:high];
NSArray *result;
// 0:low 1:high 2:sum
if ([left[2] intValue] >= [right[2] intValue] && [left[2] intValue] >= [cross[2] intValue]) {
result = left;
} else if ([right[2] intValue] >= [left[2] intValue] && [right[2] intValue] >= [cross[2] intValue]) {
result = right;
} else {
result = cross;
}
// show view
float y = self.showCounter * 30 + 90;
double delayInSeconds = 0.5 * self.showCounter + 0.5;
dispatch_time_t popTime = dispatch_time(DISPATCH_TIME_NOW, (int64_t)(delayInSeconds * NSEC_PER_SEC));
dispatch_after(popTime, dispatch_get_main_queue(), ^(void){
[self showSubarrayMax:arr Low:[result[0] intValue] high:[result[1] intValue] start:low end:high y:y];
});
self.showCounter++;
return result;
}
}
@end