算法题-1

求最大值
题目：在给定的一个长度为N(n>1)的整形数组arr，可以划分成左右两个部分，做部分为arr[0..k]，右部分为arr[k+1..N-1]，k可以取值的范围为[0..N-2], 求这么多划分方案中，左部分中的最大值减去右部分最大值的绝对值中，最大值是多少？

例如：[2,7,3,1,1]

当左部分为[2,7]，右部分为[3,1,1]时，左部分中的最大值减去右部分的最大值的绝对值为4；

当左部分为[2,7,3]，右部分为[1,1]时，左部分的最大值减去右部分的最大值的绝对值为6；

还有好多划分方案，但最终返回6.

分析：首先题目一定要看清楚。在一个整数集合中，使用整数k来把这个集合一刀两断分为两个子集， 把所有的划分方案得到的结果放到一个集合，记做集合A，把这两个子集中各自的最大值 差的绝对值放在集合A中，也就是求集合A的最大值。

复杂度做到尽量小。

最优解：

遍历一遍集合，找出最大值，在这么多分配方案中，不管这个最大值分配在左边集合还是右边集合，始终是最大值减去 这两个子集中最大值最小的的那个。假如说最大值被划到了左边集合：拿题目中的例子来说，最大值7在左边是定死的了，没办法改变了，现在要做的就是让右边集合的最大值越小越好，所以你让k值就等于N-2就可以了，也就是右边集合只留一个元素；

相反最大值被划到右边是一样的道理，左边子集留第一个元素就可以了；

然后 max = arrayMax - MIN(arr[0],arr[N-1]);求出最大；

这个max就是求出的最大值；

代码实现：

    //C代码
        int arr[] = {2,4,7,3,1,1};
        int length = sizeof(arr)/sizeof(int);
        int arrMax = 0;
        for (int i = 0; i < length; i++) {
            int temp = MAX(arr[i], arr[i+1]);
            arrMax = MAX(temp, arrMax);
        }
        int lastMax = arrMax - MIN(arr[0], arr[length-1]);
        printf("arrMax = %d, lastMax=%d",arrMax,lastMax);

//OC代码
    NSArray *intArray = @[@2,@4,@7,@3,@1,@1];
    int max = 0;
    for (int i = 0; i < intArray.count; i++) {
        if (i != intArray.count-1) {
            NSNumber *number = intArray[i] > intArray[i+1] ? intArray[i] : intArray[i+1];
            if (max < number.intValue) {
                max = number.intValue;
            }
        }
    }
    int lastM = max - MIN(((NSNumber *)([intArray firstObject])).intValue, ((NSNumber *)([intArray lastObject])).intValue);
    NSLog(@"-------%d------%d",max,lastM);

如有疑问或错误，望指正，与君共勉，谢谢！