#牛客堂直播视频#数组相关和动态规划（2015.7.8）

第一题：

计算数组的小和

【题目】

数组小和的定义如下：

例如数组s=[1,3,5,2,4,6]，在s[0]的左边小于等于s[0]的数的和为0，在s[1]的左边小于等于s[1]的数的和为1，在s[2]的左边小于等于s[2]的数的和为1+3=4，在s[3]的左边小于等于s[3]的数的和为1，在s[4]的左边小于等于s[4]的数的和为1+3+2=6，在s[5]的左边小于等于s[5]的数的和为1+3+5+2+4=15,所以s的小和=0+1+4+1+6+15=27。

给定一个数组s，实现函数返回s的小和。

第二题：

数组中未出现的最小正整数

【题目】

给定一个无序整型数组arr，找到数组中未出现的最小正整数。 

【举例】

arr=[-1,2,3,4]。返回1。

arr=[1,2,3,4]。返回5。

第三题：

数组排序之后相邻数的最大差值

【题目】

给定一个整型数组arr，返回如果排序之后，相邻两数的最大差值。 

【举例】

arr=[9,3,1,10]。如果排序，结果为[1,3,9,10]，9和3的差为最大差值，故返回6。

arr=[5,5,5,5]。返回0。

【要求】

如果arr的长度为N，请做到时间复杂度为O(N)。

第四题：