一道笔试题：求数组元素和最大的子集

Contents

1. 1. 题目
2. 2. 思路
3. 3. 代码
4. 4. 输出与分析
5. 5. 总结

题目

昨天参加腾讯旗下某公司的笔试，其中唯一的算法题是这样的（大致描述）：

某数组中有正数也有负数，相邻的一个或多个元素组成一个子集，求所有子集中元素和的最大值。
例如数组[-2, -4, 3, 5, -6, -3, 2, 4], 其子集和最大值为8,对应子集为[3, 5]

思路

第一反应是穷举，即列举所有长度从1到全集的所有子集的和，但是这肯定是效率很低的方法。

当时解题的思路就是分析人工计算时，会以何种方式进行：

1. 从第一个元素开始往后累加，更新记录过程中的最大和
   2.如果和为负，则抛弃前面的和，从后续元素开始重新累加
   3.直到数组尾，得到最大值

代码

那么用代码实现就是这样的：

package io.github.azyet;


public class App {

    static int maxSum(int a[], int len) {//求最大子集和的方法
        int max = 0;                //最大和
        int sum = 0;                //当前累加和
        int i = 0;                  //当前指针 

        while (i < len - 1 && a[i] <= 0) i++;       //从第一个正值元素开始累加
        max = a[i];                             
        sum = a[i];                                 //初始化
        i++;

        while (i < len) {                           //累加开始
            sum += a[i];                            
            if (max < sum) max = sum;               //更新最大和
            if (sum <= 0) {                         //累加和为负，则舍弃
                while(a[++i]<=0);                   //找到下一个正值元素，重新初始化
                sum = a[i++];
            }else                                   //累加和为正，则继续
                i++;
        }
        return max;
    }

    public static void main(String[] args) {
        int testArray[] = {-2, -4, 3, 5, -6, -3, 2, 4};// {20,-22,-2, -3, 4, 5, -2, -4, 8,2};
        System.out.printf("max subset sum is: %d.\n", maxSum(testArray, testArray.length));
    }
}

输出与分析

max subset sum is: 8.

从实现上看，只用了一层循环和常数个变量，因此此实现的时间性能为线性，空间性能为常数。

总结

此类题型并没有遇到过，头脑中往往会有第一反应的方法，可以简单分析一下是不是合理的方法，比如实现上的复杂程序和性能角度，如果不是很理想，就应思考更伏方法。而方式则还是根据问题去分解、分析，可模拟平日求解普通数学问题的过程，演绎得到可行方法后，再细化过程，写下详细的算法步骤，最后就可以用代码实现了。