[已解决]Python：每日一题 266

zltzlt

今天的题目：

给定一个整数数组，找出两个不重叠的子数组 A 和 B，使两个子数组和的差的绝对值（sum(A) - sum(B)）最大，并返回这个最大的差值。
注意：子数组在原数组中一定要是连在一起的。例如 [1, 1, 2] 不是 [1, 2, -3, 1] 的子数组，但 [1, 2] 是。

示例 1:

输入：[1, 2, -3, 1]
输出：6
解释：子数组是 [1, 2] 和[-3]，所以答案是 6。

示例 2：

输入：[0, -1]
输出：1
解释：子数组是 [0] 和 [-1]，所以答案是 1。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

华一仙

2019-11-2 08:13:12

答题之前，先感谢一下抽时间出题、判题的版主，以及提供过题目的鱼友们
原来“不重叠”是指“两个切片的索引没有交集”

1. from time import perf_counter  # 单位为秒
   
2. 
   
3. def cal_time(func):
   
4.     """ 懒人测时间 """
   
5.     def inn(nums):
   
6.         start = perf_counter()
   
7.         res = func(nums)
   
8.         stop = perf_counter()
   
9.         print(f">>> result = {res}, run time: {(stop - start) * 1000}ms")
   
10.     return inn
    
11. 
    
12. @cal_time
    
13. def f266(nums):
    
14.     size = len(nums)
    
15.     if size < 2:
    
16.         return None  # 以防万一，就是不知道该返回 None 还是 False
    
17. 
    
18.     minL = [0] * size
    
19.     maxL = [0] * size
    
20.     minL[0] = maxL[0] = nums[0]
    
21.     for i in range(1, size):
    
22.         minL[i] = min(minL[i-1] + nums[i], nums[i])  # minL[i] 存放 nums[:i+1] 的切片的最小值，其余三个同理
    
23.         maxL[i] = max(maxL[i-1] + nums[i], nums[i])
    
24. 
    
25.     minR = [0] * size
    
26.     maxR = [0] * size
    
27.     minR[-1] = maxR[-1] = nums[-1]
    
28.     for i in range(size - 2, -1, -1):
    
29.         minR[i] = min(minR[i+1] + nums[i], nums[i])
    
30.         maxR[i] = max(maxR[i+1] + nums[i], nums[i])
    
31. 
    
32.     res = float("-inf")
    
33.     for i in range(size - 1):
    
34.         res = max(res, abs(maxL[i] - minR[i + 1]), abs(minL[i] - maxR[i + 1]))
    
35.     return res
    
36. 
    
37. if __name__ == "__main__":
    
38.     arr1 = [-2, 0, 0, 1, -1, -1]  # 3
    
39.     arr2 = [-5, -4]  # 1
    
40.     arr3 = [1, 2, -3, 1]  # 6
    
41. 
    
42.     f266(arr3)

复制代码

跳转到最佳答案楼层

Unicorn#

空数组算子数组吗

zltzlt

Unicorn# 发表于 2019-10-30 20:37
空数组算子数组吗

不算。

塔利班

1. def f(L):
   
2.     L=list(set(sorted(L)))
   
3.     s=L[0]*L[-1]
   
4.     if s>0:
   
5.         L.sort(key=abs)
   
6.         B=L[:1]
   
7.         A=L[1:]
   
8.     elif s<0:
   
9.         A=[x for x in L if x<0]
   
10.         B=[x for x in L if x>0]
    
11.     else:
    
12.         A=[0]
    
13.         B=L
    
14.     return abs(sum(A)-sum(B))

复制代码

1. def f(L):
   
2.     L=list(set(sorted(L)))
   
3.     P=[x for x in L if x>=0]
   
4.     N=[x for x in L if x<0]
   
5.     if P and N:
   
6.         return sum(P)-sum(N)
   
7.     elif P:
   
8.         return sum(P[1:])-P[0]
   
9.     else:
   
10.         return N[-1]-sum(N[:-1])

复制代码

Unicorn#

终极蛇皮之上帝视角之小甲鱼听了想打人之时间宝石之四重循环暴力解法（手动滑稽）

1. def solve(S):
   
2.     m = 0
   
3.     tail = len(S)
   
4.     for i in range(tail-1):
   
5.         a = 0
   
6.         for j in range(i, tail-1):
   
7.             a += S[j]
   
8.             for k in range(j+1, tail):
   
9.                 b = 0
   
10.                 for r in range(k, tail):
    
11.                     b += S[r]
    
12.                     temp = abs(a-b)
    
13.                     if temp > m:
    
14.                         m = temp
    
15.     return m

复制代码

阴阳神万物主

关于数组的部分有疑问，百度百科：数组 我记得在同一个数组中可以出现相同的元素，那么，示例1 中的 子数组 A 为 [1,1,2] B 为 [-3] 时的差值才是最大的，为7，不是吗？

阴阳神万物主

就目前而言，我读题理解出的意思为：求给定全集的两个交集为空的子集，使得两个集合间元素总和的差值最大
不晓得对不对，如果不对，我再改

1. def solve(put:list,who:bool =False)->int:
   
2.     temp = list(set(put))
   
3.     temp.sort()
   
4.     B = [x for x in temp if x<=0 ]
   
5.     if len(B) == len(temp):
   
6.         if who:
   
7.             print('A =',list(temp[-1]),'B = ',B[:-1])
   
8.         return temp[-1] - sum(B[:-1])
   
9.     elif not len(B):
   
10.         if who:
    
11.             print('A =',temp[1:],'B = ',[temp[0]])
    
12.         return sum(temp[1:]) - temp[0]
    
13.     else:
    
14.         if who:
    
15.             print('A =',temp[len(B):],'B = ',B)
    
16.         return sum(temp[len(B):]) - sum(B)
    
17. 
    
18. if __name__ == '__main__':
    
19.     print('示例1 输出：',solve([1,2,-3,1]))
    
20.     print('示例2 输出：',solve([0,-1]))
    

复制代码

简化一下代码，美化一下：

1. def solve(put:list,who:bool =False)->int:
   
2.     temp = list(set(put))
   
3.     temp.sort()
   
4.     B = [x for x in temp if x<=0 ]
   
5.     if len(B) == len(temp):
   
6.         A,B = [temp[-1]], B[:-1]
   
7.     elif not len(B):
   
8.         A,B = temp[1:] , [temp[0]]
   
9.     else:
   
10.         A,B = temp[len(B):] , B
    
11.     if who:
    
12.         print('A =',A,'B = ',B)
    
13.     return sum(A) - sum(B)
    
14. 
    
15. if __name__ == '__main__':
    
16.     print('示例1 输出：',solve([1,2,-3,1]))
    
17.     print('示例2 输出：',solve([0,-1]))
    

复制代码

18511353234

阴阳神万物主 发表于 2019-10-30 21:11
关于数组的部分有疑问，百度百科：数组 我记得在同一个数组中可以出现相同的元素，那么，示例1 中的 子数组 ...

有同样的疑问

panheng

1. def answer(lst: list):
   
2.     res = 0
   
3.     lenth = len(lst)
   
4.     for i in range(0, lenth - 1):
   
5.         for j in range(i + 1, lenth + 1):
   
6.             temp = abs(sum(lst[:i + 1]) - sum(lst[i + 1:j]))
   
7.             if temp > res and (i + 1) != j:
   
8.                 res = temp
   
9.     return res

复制代码

panheng

18511353234 发表于 2019-10-31 07:09
有同样的疑问

python里数组是有序序列，所以子组不是集合中子集概念，这题可以理解为切块

panheng

阴阳神万物主 发表于 2019-10-30 21:36
就目前而言，我读题理解出的意思为：求给定全集的两个交集为空的子集，使得两个集合间元素总和的差值最大
...

肯定理解错了。
1、你说的两个集合中可能出现相同元素。
2、按你的逻辑只要筛选出正、负元素即可，当无负数则拿出最小1个元素，用全部和减去两次最小值

776667

1. def fun266(list_x):
   
2.     list_x = list(set(list_x))
   
3.     max_list = [i for i in list_x if i > 0]
   
4.     if not max_list:
   
5.         max_list.append(max(list_x))
   
6.     min_list = [i for i in list_x if i < 0]
   
7.     if not min_list:
   
8.         min_list.append(min(list_x))
   
9.     return abs(sum(max_list) - sum(min_list))

复制代码

阴阳神万物主

panheng 发表于 2019-10-31 10:03
肯定理解错了。
1、你说的两个集合中可能出现相同元素。
2、按你的逻辑只要筛选出正、负元素即可，当无 ...

交集为空，就代表没有重样的部分；就是两集合的元素互不相同；其中一个集合中的任意元素，在另一个集合中都不存在。

最后的魁拔

想问一下，每日一题适合新手吗？      

阴阳神万物主

最后的魁拔 发表于 2019-10-31 10:25
想问一下，每日一题适合新手吗？

你往题号小的找，题号小的难度相对较低

最后的魁拔

阴阳神万物主 发表于 2019-10-31 10:36
你往题号小的找，题号小的难度相对较低

o了

EmperorAA

def fun1(*a):
    if len(a) < 2:
        raise ValueError()
    else:
        a = list(set(a))
        a.sort()
        L = [a[0]]
        R = [a[len(a)-1]]
        if len(a) > 2:
            for i in range(1,len(a)-1):
                if a[i] > 0:
                    break
            L = a[0:i]
            R = a[i:len(a)-1]
    return sum(R)- sum(L)

动心成神

1. def fun(A):
   
2.     if len(list(filter(lambda x:x>=0,A)))!=0 and len(list(filter(lambda x:x<=0,A)))!=0:
   
3.         return sum(set(filter(lambda x:x>=0,A)))-sum(set(filter(lambda x:x<=0,A)))
   
4. 
   
5.     elif len(list(filter(lambda x:x>=0,A)))==0:
   
6.         return max(A)-sum(set(filter(lambda x:x<max(A),A)))
   
7.     elif len(list(filter(lambda x:x<=0,A)))==0:
   
8.         return sum(set(filter(lambda x: x > min(A), A)))-min(A)
   
9. 
   
10. A = [1,2,-3,1]
    
11. print(fun(A))

复制代码

动心成神

针对输入都是同一个数时做了修正。

1. def fun(A):
   
2.     if max(A)==min(A):
   
3.         return '您测试的数据不和法！'
   
4.     else:
   
5.         if len(list(filter(lambda x:x>=0,A)))!=0 and len(list(filter(lambda x:x<=0,A)))!=0:
   
6.             return sum(set(filter(lambda x:x>=0,A)))-sum(set(filter(lambda x:x<=0,A)))
   
7. 
   
8.         elif len(list(filter(lambda x:x>=0,A)))==0:
   
9.             return max(A)-sum(set(filter(lambda x:x<max(A),A)))
   
10. 
    
11.         elif len(list(filter(lambda x:x<=0,A)))==0:
    
12.             return sum(set(filter(lambda x: x > min(A), A)))-min(A)
    
13. 
    
14. A = [1,1,2,1]
    
15. print(fun(A))

复制代码

阴阳神万物主

预订题号为268的题目，题目来源 ：洛谷 P1538 迎春舞会之数字舞蹈
题目背景 HNSDFZ的同学们为了庆祝春节，准备排练一场舞会。

题目描述 在越来越讲究合作的时代，人们注意的更多的不是个人物的舞姿，而是集体的排列。
为了配合每年的倒计时，同学们决定排出——“数字舞蹈”。顾名思义就是所有人一起排成若干个数字 -___-||||  更为创新的是，每个人都是趴在地上，保证横竖。
现在给出数字及其要求摆出的大小，请你编程，模拟同学们的优美姿态。

输入 略
输出略

测试数据.zip (452.32 KB, 下载次数: 2)

2019-10-31 12:42 上传

点击文件名下载附件

解压密码还是之前的，已有的一组输入输出，为示例。