最長増加部分列をパラパラめくりで表示してみようと試みた。。。iPhoneアプリのサンプルコードを描いてみます。
#import “ViewController.h”
#include <memory>
#include <algorithm>
#define MAXN 100
#define INF 10000
using namespace std;
class LISSolver {
public:
int lastNumber;
int size;
int dp[MAXN];
void solve(NSArray*);
};
void LISSolver::solve(NSArray *arr) {
if (!arr) {
return;
}
int n = (int)arr.count;
fill(dp, dp + MAXN, INF);
for (NSNumber *a in arr) {
*lower_bound(dp, dp + n, [a intValue]) = [a intValue];
}
size = (int)(lower_bound(dp, dp + n, INF) – dp);
lastNumber = dp[size – 1];
};
@interface ViewController ()
@property (nonatomic, strong) NSMutableArray *numbers;
@end
@implementation ViewController
– (void)viewDidLoad {
[super viewDidLoad];
self.view.backgroundColor = [UIColor colorWithHue:0.25 saturation:1 brightness:0.3 alpha:1];
UILabel *title = [[UILabel alloc] init];
title.font = [UIFont systemFontOfSize:22];
title.textColor = [UIColor whiteColor];
title.text = @”Longest Increasing Subsequence”;
[title sizeToFit];
title.center = CGPointMake(CGRectGetMidX(self.view.bounds), 70);
[self.view addSubview:title];
self.numbers = [NSMutableArray array];
for (int i=0; i<64; i++) {
int number = arc4random() % 100 + 1;
[self.numbers addObject:@(number)];
float x = ((i % 8) + 1) * CGRectGetMaxX(self.view.bounds) / 10;
float y = (i / 8) * CGRectGetMaxX(self.view.bounds) / 10 + 100;
UILabel *l = [[UILabel alloc] initWithFrame:CGRectMake(x, y, 30, 30)];
l.tag = number;
l.text = [NSString stringWithFormat:@”%d”, number];
l.textAlignment = NSTextAlignmentCenter;
l.backgroundColor = [UIColor colorWithHue:0.1 * (i % 10) saturation:0.2 brightness:1 alpha:1];
[self.view addSubview:l];
}
}
– (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event
{
shared_ptr<LISSolver> cppClass(new LISSolver());
cppClass->solve(self.numbers);
// calc
int last = cppClass->lastNumber;
// for animation …..
NSArray *numberLabelArr = [self.view.subviews filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@”tag > 0″]];
for (int i=0; i<numberLabelArr.count; i++) {
int idx = (int)numberLabelArr.count – i – 1;
UIView *v = numberLabelArr[idx];
if (v.tag > 0) {
if (v.tag == last) {
if (idx > 1) {
NSArray *subArr = [self.numbers subarrayWithRange:NSMakeRange(0, idx)];
subArr = [subArr filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@”self < %d”, last]];
cppClass->solve(subArr);
last = cppClass->lastNumber;
}
continue;
}
[UIView animateWithDuration:0.2 delay:i * 0.1 options:0 animations:^{
v.layer.transform = CATransform3DMakeRotation(M_PI * 0.5, 0, 1, 0);
} completion:nil];
}
}
}
@end