Maximum subarray

Category: Array

Deadline: 1st week (12/31 - 1/7)

Difficulty: Easy

Github: https://github.com/iamseokhyun/2022-algorithm-study/tree/master/array/MaximumSubarray/

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

Problem

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 1:

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

Output: 6

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

Example 2:

Input: nums = [1]

Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]

Output: 23

Constraints:

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

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.

Solution

public class Solution
{
    public int MaxSubArray(int[] nums)
    {
        if (nums.Length == 1)
        {
            return nums[0];
        }

        int[] subtotal = new int[nums.Length];
        int tmp = 0;

        for (int i = 0; i < nums.Length; i++)
        {
            tmp += nums[i];
            subtotal[i] = tmp;
        }

        int res = int.MinValue;
        int min = int.MaxValue;
        bool up = false;

        for (int i = 0; i < subtotal.Length; i++)
        {
            if (subtotal[i] < min)
            {
                min = subtotal[i];
            }
            else if (res < subtotal[i] - min)
            {
                up = true;
            }

            res = subtotal[i] - min;
        }

        if (up == false)
        {
            int small = int.MinValue;

            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] > small)
                {
                    small = nums[i];
                }
            }

            return small;
        }

        return res;
    }
}

Comment

• subtotal : subtotal[i] = 0~ith index까지의 수열의 합이라고 두자. subtotal에서 가장 차이가 많이 나는 index를 선택하면 Maximum subarray를 얻을 수 있을 것이다.
• 기본적인 idea는 “Best time to buy and sell stocks”와 동일, 차이점은 Stock 문제에서는 계속 감소하는 수열([5,4,3,2,1])이 주어지면 아예 주식을 구매하지 않으면 되지만, 이 문제의 경우 subtotal이 계속 감소한다 하더라도 결국 1개는 선택해야만 함. -> up 이라는 bool marker를 만들어 한번이라도 up을 치지 않는다면, subtotal이 단감소수열이므로, 가장 차가 적은 값을 선택하도록 추가함.