algorithms/053-maximum-subarray.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "third-condition",
   "metadata": {},
   "source": [
    "### 最大子序和\n",
    "\n",
    "#### 示例 1：\n",
    "```\n",
    "输入：nums = [-2,1,-3,4,-1,2,1,-5,4]\n",
    "输出：6\n",
    "解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。\n",
    "```\n",
    "\n",
    "#### 示例 2：\n",
    "```\n",
    "输入：nums = [1]\n",
    "输出：1\n",
    "```\n",
    "\n",
    "#### 示例 3：\n",
    "```\n",
    "输入：nums = [0]\n",
    "输出：0\n",
    "```\n",
    "\n",
    "#### 示例 4：\n",
    "```\n",
    "输入：nums = [-1]\n",
    "输出：-1\n",
    "```\n",
    "\n",
    "#### 示例 5：\n",
    "```\n",
    "输入：nums = [-100000]\n",
    "输出：-100000\n",
    "```\n",
    "#### 提示：\n",
    "- $1 <= nums.length <= 3 * 10^4$\n",
    "- $-10^5 <= nums[i] <= 10^5$\n",
    "\n",
    "进阶：如果你已经实现复杂度为`O(n)`的解法，尝试使用更为精妙的**分治法**求解"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "secure-retention",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "def maxSubArray2(nums: List[int]) -> int:\n",
    "    n = len(nums)\n",
    "    if n < 1:\n",
    "        return 0\n",
    "    elif n == 1:\n",
    "        return nums[0]\n",
    "    \n",
    "    dp = [nums[0] for _ in range(n)]\n",
    "    for i in range(1, n):\n",
    "        dp[i] = max(nums[i], dp[i - 1] + nums[i])\n",
    "    \n",
    "    return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "desperate-identification",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxSubArray(nums: List[int]) -> int:\n",
    "    n = len(nums)\n",
    "    if n < 1:\n",
    "        return 0\n",
    "    elif n == 1:\n",
    "        return nums[0]\n",
    "    \n",
    "    ans = -100000\n",
    "    pre = nums[0]\n",
    "    for i in range(1, n):\n",
    "        pre = max(nums[i], pre + nums[i])\n",
    "        ans = max(pre, ans)\n",
    "    \n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "friendly-electronics",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-100000"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maxSubArray([-100000])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "atomic-liability",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maxSubArray([-2,1,-3,4,-1,2,1,-5,4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "sharing-typing",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maxSubArray([1, -2, 3, 5, -2, 6, -1])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}