---
title: 'LeetCode 53. Maximum Subarray'
disqus: hackmd
---

# LeetCode 53. Maximum Subarray

## Description

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

A subarray is a contiguous part of an array.

## Example

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

## Constraints

1 <= nums.length <= 10^5^
-10^4^ <= nums[i] <= 10^4^

## Answer

只看疊加值是否小於現值，若小於現值表示從現值開始重算就會變更大，故更新sum為現值，若大於現值就繼續疊加，且每次都判斷max。

//2022_03_29
int maxSubArray(int* nums, int numsSize){
    int max = *nums, sum = *nums++;
    for(int i = 1; i < numsSize; i++, nums++){
        sum = sum > 0 ? sum + *nums : *nums;
        max = max > sum ? max : sum;
    }
    return max;
}

## Link
https://leetcode.com/problems/maximum-subarray/
###### tags: `Leetcode`