[leetcode - C] Maximum Subarray

문제 설명

https://leetcode.com/problems/maximum-subarray/

Maximum Subarray - LeetCode

 

• 난이도 - Medium

배열에서 연속된 수들 중 합이 가장 큰 조합을 찾는 문제

---

관련 개념

배열

---

접근 방법

패턴을 찾으면 구현은 어렵지 않은 문제.

배열의 요소를 앞에서부터 탐색하면서 현재 탐색하는 수를 Maximum Subarray에 포함할지 말지가 관건

이므로, (직전까지의 누적합+현재 수) 와 (현재 수)를 비교해서 둘 중 큰 수가 새로운 누적합이 됨.

---

답안 코드

Runtime: 174 ms (39.15%)
Memory Usage: 12.2 MB (75.56%)

int maxSubArray(int* nums, int numsSize){
    int sum=-10000;
    int max=-10000;
    
    for(int i=0; i<numsSize; i++){
        sum = sum+nums[i] < nums[i] ? nums[i] : sum + nums[i];
        max = max < sum ? sum : max;
    }
    
    return max;
}