在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding

本文为大家介绍其中的 第44题：最大边权和 的题目解析，具体如下：

题目描述

题目等级：容易
知识点：贪心

查看题目：最大边权和
现在有n个点(1<=n<=1000)，每个点都有一个值称为点权ai(ai为偶数，1<=ai<=1000)，现在可以将任意两个点相连，连起来以后这条边也有一个值称为边权，这个边的边权为这两个点的点权之和的一半。现在需要你添加n-1条边，问将这n个点连通以后(连通是指任意两个点都能互相到达)的最大的边权和是多少?

输入点的数量n；和n个数，表示点权的值

输出最大的边权和

示例1
输入：
5
[2,4,6,8,10]
输出：
30

解题思路：贪心

根据题意，最终需要将n个点连通并达到最大边权，而边权为两个点的点权之和的一半，所以一个点加入连通图的最大边权就是和点权最大的点连通。

因此想要得到最大边权和，只要所有点都与点权最大的点相连即可。

实现过程中，首先求出最大的点权，然后计算出其他点与这个权值最大的点的边权之和即可。

时间复杂度：O(n)
空间复杂度：O(1)

看完之后是不是有了想法了呢，快来练练手吧>>查看题目：最大边权和