# 问题

1.png

2.png

#### 算法1

```- (int)maxSubsequenceSumFirst:(NSArray *)array
{
int subSum, maxSum, i, j, k;
NSInteger count = array.count;
maxSum = 0;
for (i = 0; i < count; i++) {
for (j = i; j < count; j++) {
subSum = 0;
for (k = i; k <= j; k++) {
subSum += [array[k] intValue];
}

if (subSum > maxSum) {
maxSum = subSum;
}
}
}
return maxSum;
}```

#### 算法2

```- (int)maxSubsequenceSumSecond:(NSArray *)array
{
int subSum, maxSum, i, j;
NSInteger count = array.count;

maxSum = 0;
for (i = 0; i < count; i++) {
subSum = 0;
for (j = i; j < count; j++) {
subSum += [array[j] intValue];

if (subSum > maxSum) {
maxSum = subSum;
}
}
}
return maxSum;
}```

# 算法3

```- (int)maxSubsequenceSumThird:(NSArray *)array
{
int right = (int)array.count - 1;
return [self maxSubSum:array left:0 right:right];
}

- (int)maxSubSum:(NSArray *)array left:(int)left right:(int)right
{
int maxLeftSum, maxRightSum;
int maxLeftBorderSum, maxRightBorderSum;
int leftBorderSum, rightBorderSum;
int center, i;

if (left == right) { //基本情况，左右相同，说明只有一个元素
if (array[left] > 0) {
return [array[left] intValue];
} else {
return 0;
}
}

center = (left + right ) / 2;
maxLeftSum = [self maxSubSum:array left:left right:center];
maxRightSum = [self maxSubSum:array left:center + 1 right:right];

maxLeftBorderSum = 0;
leftBorderSum = 0;
for (i = center; i >= left; i--) {
leftBorderSum += [array[i] intValue];
if (leftBorderSum > maxLeftBorderSum) {
maxLeftBorderSum = leftBorderSum;
}
}

maxRightBorderSum = 0;
rightBorderSum = 0;
for (i = center + 1; i <= right; i++) {
rightBorderSum += [array[i] intValue];
if (rightBorderSum > maxRightBorderSum) {
maxRightBorderSum = rightBorderSum;
}
}

int max = MAX(maxLeftSum, maxRightSum);

return MAX(maxLeftBorderSum + maxRightBorderSum, max);
}```

#### 算法4

```- (int)maxSubsequenceSumFourth:(NSArray *)array
{
int subSum, maxSum, j;
subSum = maxSum = 0;

for(j = 0; j < array.count ; j++) {
subSum  += [array[j] intValue];

if (subSum > maxSum) {
maxSum = subSum;
} else if (subSum < 0) {
subSum = 0;
}
}

return maxSum;
}```

# 实际运行时间

```2016-06-24 16:35:29.510 PractiseProject[4195:185619] 数组中元素的个数:10
2016-06-24 16:35:29.510 PractiseProject[4195:185619] 算法一运行时间：1.7808e-05 秒,计算结果:23
2016-06-24 16:35:29.510 PractiseProject[4195:185619] 算法二运行时间：5.098e-06 秒,计算结果:23
2016-06-24 16:35:29.511 PractiseProject[4195:185619] 算法三运行时间：8.092e-06 秒,计算结果:23
2016-06-24 16:35:29.511 PractiseProject[4195:185619] 算法四运行时间：2.909e-06 秒,计算结果:23```

```2016-06-24 16:36:20.751 PractiseProject[4217:186946] 数组中元素的个数:28
2016-06-24 16:36:20.751 PractiseProject[4217:186946] 算法一运行时间：0.000150832 秒,计算结果:114
2016-06-24 16:36:20.751 PractiseProject[4217:186946] 算法二运行时间：1.8889e-05 秒,计算结果:114
2016-06-24 16:36:20.751 PractiseProject[4217:186946] 算法三运行时间：1.808e-05 秒,计算结果:114
2016-06-24 16:36:20.752 PractiseProject[4217:186946] 算法四运行时间：3.782e-06 秒,计算结果:114```

```2016-06-24 16:37:21.658 PractiseProject[4234:187666] 数组中元素的个数:100
2016-06-24 16:37:21.663 PractiseProject[4234:187666] 算法一运行时间：0.00419705 秒,计算结果:1204
2016-06-24 16:37:21.663 PractiseProject[4234:187666] 算法二运行时间：0.000202042 秒,计算结果:1204
2016-06-24 16:37:21.663 PractiseProject[4234:187666] 算法三运行时间：6.589e-05 秒,计算结果:1204
2016-06-24 16:37:21.664 PractiseProject[4234:187666] 算法四运行时间：7.354e-06 秒,计算结果:1204```

```2016-06-24 16:38:00.642 PractiseProject[4249:188454] 数组中元素的个数:1000
2016-06-24 16:38:04.816 PractiseProject[4249:188454] 算法一运行时间：4.1736 秒,计算结果:32133
2016-06-24 16:38:04.829 PractiseProject[4249:188454] 算法二运行时间：0.0124339 秒,计算结果:32133
2016-06-24 16:38:04.829 PractiseProject[4249:188454] 算法三运行时间：0.00054806 秒,计算结果:32133
2016-06-24 16:38:04.829 PractiseProject[4249:188454] 算法四运行时间：3.9842e-05 秒,计算结果:32133```

```2016-06-24 16:39:03.479 PractiseProject[4265:189178] 数组中元素的个数:10000
2016-06-24 16:38:04.816 PractiseProject[4249:188454] 算法一运行时间：NA,计算结果:未知
2016-06-24 16:39:04.714 PractiseProject[4265:189178] 算法二运行时间：1.23446 秒,计算结果:852859
2016-06-24 16:39:04.719 PractiseProject[4265:189178] 算法三运行时间：0.00523675 秒,计算结果:852859
2016-06-24 16:39:04.720 PractiseProject[4265:189178] 算法四运行时间：0.000379842 秒,计算结果:852859```

```2016-06-24 16:40:36.132 PractiseProject[4284:190117] 数组中元素的个数:100000
2016-06-24 16:38:04.816 PractiseProject[4249:188454] 算法一运行时间：NA,计算结果:未知
2016-06-24 16:42:40.983 PractiseProject[4284:190117] 算法二运行时间：124.846 秒,计算结果:14896405
2016-06-24 16:42:41.046 PractiseProject[4284:190117] 算法三运行时间：0.0624209 秒,计算结果:14896405
2016-06-24 16:42:41.049 PractiseProject[4284:190117] 算法四运行时间：0.00294211 秒,计算结果:14896405```

# 补充

```/**
*  生成一个有count个元素的数组
*
*  @param count 个数
*
*  @return 数组
*/
- (NSArray *)arrayWithCount:(NSInteger)count
{
NSMutableArray *array = [NSMutableArray arrayWithCapacity:count];
if (count <= 0) {
return array;
}
for (int i = 0; i < count; i++) {
int number = arc4random() % count;
int random = arc4random() % 2;
if (random == 0) {
number *= -1;
}

}

return array;
}```

```    int n = 100;
NSArray *randomArray = [self arrayWithCount:n];
NSLog(@"数组中元素的个数:%d",n);
CFTimeInterval startTime =  CACurrentMediaTime();
int one = [self maxSubsequenceSumFirst:randomArray];
CFTimeInterval endTime = CACurrentMediaTime();
NSLog(@"算法一运行时间：%g 秒,计算结果:%d", endTime - startTime, one);

startTime =  CACurrentMediaTime();
int two = [self maxSubsequenceSumSecond:randomArray];
endTime = CACurrentMediaTime();
NSLog(@"算法二运行时间：%g 秒,计算结果:%d", endTime - startTime, two);

startTime =  CACurrentMediaTime();
int three = [self maxSubsequenceSumThird:randomArray];
endTime = CACurrentMediaTime();
NSLog(@"算法三运行时间：%g 秒,计算结果:%d", endTime - startTime, three);

startTime =  CACurrentMediaTime();
int four = [self maxSubsequenceSumFourth:randomArray];
endTime = CACurrentMediaTime();
NSLog(@"算法四运行时间：%g 秒,计算结果:%d", endTime - startTime, four);```

70 篇文章16 人订阅

0 条评论

## 相关文章

4312

3996

### 枚举

​ 枚举就是尝试所有的可能性，尤其是当我们在确定一个问题是不是的这一类问题中尤其有用，例如说给一堆数，让我我们判断他们是不是素数，或者素数的数量的时候，这...

3196

4129

1052

3464

2884

5516

### 20:反反复复

20:反反复复 总时间限制: 1000ms 内存限制: 65536kB描述 Mo和Larry发明了一种信息加密方法。他们首先决定好列数，然后将信息（只包含字...

3858

1372