题解 | #最大四边形面积#

题目：最大四边形面积
描述：给定大小为n的整数集合A，代表n根木棍的长度。从A中任选4根木棍组成一个四边形，求其面积最大为多少。数据保证有解。
程序返回结果与正确答案的误差应小于0.00001
示例1：输入：[1,2,3,4,5]，返回值：10.95445

解法一：
思路分析+实例分析：该题目的意思是求解存在的最大四边形的面积，因为题目中给定大小为n的整数集合代表木棍的长度，从整数集合A中任意选取4根木棍组成四边形，在计算这道数学题的过程中，我们首先应该明白什么叫四边形，四边形的判定条件是什么，任意四边形的面积是怎么计算，所以笔者去查阅了相关资料做出以下解释。
众所周知，对于指定的三条边a，b，c，它首尾相接可以构成一个三角形的条件是：

a < b + c，b < a + c，c < a + b 这就是我们学的三角形两边之和大于第三边的结论，在四边形中，我们仍然可以引用上面的几何公理，由此得到一个必要条件就是： a < b + c + d，b < a + c + d，c < a + b + d，d < a + b + d 具体的判定过程就不进行一一分析了，我们直接进行使用。下面进行四边形面积的分析，因为这道题中给定了一个条件就是四边形的边长都已经给定了，所以我们采用的公式如下图所示：

图片说明
通过上述分析，我们已经具备了写程序的所有条件，下面展示程序。
C++核心程序为：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @return double浮点型
     */
    double F(double a,double b,double c,double d){
        if(a + b + c < d||a + b + d < c || a + c + d < b || b + c + d < a)
            //不满足形成四边形的条件
            return 0.0;
        double z = (a + b + c + d) / 2;//z值得计算条件
        return sqrt((z-a)*(z-b)*(z-c)*(z-d));
    }

    double solve(vector<int>& a) {
        // write code here
         int len = a.size();//a数组得长度
         double  res = 0;//最终结果
        for(int i = 0;i < len - 3;i++)//四层嵌套循环
            for(int j = i + 1;j < len - 2;j++)
                for(int k = j + 1;k < len - 1;k++)
                    for(int l = k + 1;l < len;l++)
                    {
                        res = max(res,F(a[i],a[j],a[k],a[l]));
                    }
        return res;
    }
};

在该算法中，因为有四层嵌套的for循环，所以其循环次数为 $图片说明$ ,但是在其中有重复的数组不需要进行计算，即当i等于0的值的时候，j不等于0的值等等，就相当于从n个数字中寻找不重复的四个数字，所以其时间复杂度为 $图片说明$ ，因为不需要任何额外的存储空间，所以其空间复杂度为 $O(1)$ 。

解法二：
思路分析:我们对解法一进行优化，因为我们知道，既然选择最大面积，所以我们可以初始化的时候，对数组进行排序，对数组中的元素进行倒排序（从大到小），可以节省很多时间，sort(a.rbegin(), a.rend())，然后初始化一个指针i，从3开始判断，因为前面至少还需要三个数，才能组成四条边的四边形，同样我们使用上述公式，在满足四边形的基本条件下，求解z和面积。
C++核心代码为：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @return double浮点型
     */
    double solve(vector<int>& a) {
        // write code here
        sort(a.rbegin(), a.rend());//首先进行排序，倒序
        for (int i = 3; i < a.size(); ++i) {//因为必须有4条边，所以i的值为3
            if (a[i - 3] < a[i - 2] + a[i - 1] + a[i]) {//判断满足的条件
                double z = (a[i - 3] + a[i - 2] + a[i - 1] + a[i]) / 2.0;
                //计算得到z的大小，通过公式进行计算
                return sqrt((z - a[i - 3]) * (z - a[i - 2]) * (z - a[i - 1]) * (z - a[i]));
            }
        }
        return 0;
    }
};

在上述算法中，只需要循环一次，便可以计算出最大值，因为采用了sort排序，sort排序的时间复杂度为 $O(NlogN)$ ，所以时间复杂度为 $O(NlogN)$ ，不需要占用额外的内存空间，所以其空间复杂度为 $O(1)$ 。