1、题目

53. Maximum Subarray——Easy

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],

Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

2、我的解法

(1)超时的暴力解法

 # -*- coding: utf-8 -*-

 # @Time    : 2020/2/6 22:15

 # @Author  : SmartCat0929

 # @Email   : 1027699719@qq.com

 # @Link    : https://github.com/SmartCat0929

 # @Site    :

 # @File    : 53. Maximum Subarray(超时的暴力算法）.py

 from typing import List

 class Solution:

     def maxSubArray(self, nums: List[int]) -> int:

         maxSum = -9999999999

         if len(nums)>1:

             maxSum = -99999

             for i in range(0, len(nums)):

                 for j in range(i, len(nums)):

                     thisSum = sum(nums[i:j+1])

                     if thisSum > maxSum:

                         maxSum = thisSum

             return maxSum

         elif len(nums)==1:

             maxSum=nums[0]

             return maxSum

         else:

             return 0

 print(Solution().maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))

（2）局部最大值（copy大神）

 # -*- coding: utf-8 -*-

 # @Time    : 2020/2/7 16:12

 # @Author  : SmartCat0929

 # @Email   : 1027699719@qq.com

 # @Link    : https://github.com/SmartCat0929

 # @Site    :

 # @File    : 53. Maximum Subarray.py

 from typing import List

 class Solution:

     def maxSubArray(self, nums: List[int]) -> int:

         n = len(nums)

         tmp = 0

         res = float('-inf')

         for i in range(n):

             if tmp < 0:

                 tmp = 0

             tmp = tmp + nums[i]

             res = max(res, tmp)

         return res

 print(Solution().maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))

最新文章

  1. UIScrollView的代理（delegate）
  2. ActiveMQ初体验
  3. Java--剑指offer（2）
  4. 模态视图（modalTrasitionStyle）如何适应不同的版本
  5. sql 执行动态语句
  6. 并行程序设计模式--Master-Worker模式
  7. Struts2拦截器Interceptor执行顺序理解
  8. hiho_1051_补提交卡
  9. 【OpenCV入门教程之二】 一览众山小：OpenCV 2.4.8组件结构全解析
  10. HDU-1078
  11. jsonp+handler 的实现
  12. Android开发 学习笔记——HelloWorld
  13. PC版模块滚动不显示滚动条效果
  14. mysql基础整理01
  15. Java名称字符串进行星号处理
  16. SpringCloud无废话入门01：最简SpringCloud应用
  17. Java并发编程笔记之ArrayBlockingQueue源码分析
  18. python中#!/usr/bin/python与#!/usr/bin/env python的区别
  19. Linux snprintf使用总结
  20. ZZNU 2095 : 我只看看不写题

热门文章

  1. 【STM32H7教程】第59章 STM32H7的DAC基础知识和HAL库API
  2. Codeforces Round #570 (Div. 3) B. Equalize Prices
  3. 开发板上如何配置apahe2+mysql+php7
  4. 在Linux系统下安装jdk并配置环境变量
  5. 整合SSM2
  6. [人物存档]【AI少女】【捏脸数据】人物鉴赏190
  7. webview在compileSdkVersion 大于等于23 android6.0以上系统执行js代码异常，但是在compileSdkVersion小于23 android6.0以下系统却执行正常问题
  8. SpringCloud Netflix Ribbon
  9. [python]Python 字典(Dictionary) update()方法
  10. 7_2 最大乘积（UVa11059）&lt;枚举连续子序列&gt;