Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day 17 "169. Majority Element" starting from zero

Basically, I would like to solve the easy acceptance in descending order.

problem

53. Maximum Subarray

The difficulty level is easy. One of the Top 100 Liked Questions.

Given an array of integers only nums. The problem is to find a sub-array in that array that has a maximum sum that contains at least one number, and return that sum.

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

For example, if you add all the consecutive elements from nums [3] to nums [6], you get 4 + (-1) + 2 + 1 = 6, which is the maximum value in the array. It will be a calculation.

solution

I'm a Zub amateur about dynamic programming, but I happened to read it. [Data Structures and Algorithms (New Information and Communication Systems Engineering) (Japanese)](https://www.amazon.co.jp/%E3%83%87%E3%83%BC%E3%82%BF% E6% A7% 8B% E9% 80% A0% E3% 81% A8% E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0-% E6% 96% B0% E3% 83% BB% E6% 83% 85% E5% A0% B1-% E9% 80% 9A% E4% BF% A1% E3% 82% B7% E3% 82% B9% E3% 83% 86% E3% 83% A0% E5% B7% A5% E5% AD% A6-% E4% BA% 94% E5% 8D% 81% E5% B5% 90-% E5% 81% A5% E5% A4% AB / dp / 4901683497) [Organize typical DP (Dynamic Programming) patterns Part 1 ~ Knapsack DP ~](https://qiita.com/drken/items/a5e6fe22863b7992efdb#3-%E9%83%A8%E5%88 % 86% E5% 92% 8C% E5% 95% 8F% E9% A1% 8C% E3% 81% A8% E3% 81% 9D% E3% 81% AE% E5% BF% 9C% E7% 94% A8 % E3% 81% 9F% E3% 81% A1) Well, it doesn't look like it can be solved! ?? I thought, so I thought about it while referring to it.

First, prepare the maximum value max_num and the temporary variable temp. Substitute the elements of the array so that they are licked from the beginning. If temp is 0 or more, compare it with max_num and temp, and the larger one is assigned to max_num, otherwise 0 is assigned to temp. If you try to write such a flow, it will be as follows.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        temp = 0
        max_num = max(nums)
        for i in range(len(nums)):
            temp += nums[i]
            if temp >= 0:
                max_num = max(max_num,temp)
            else:
                temp = 0
        return max_num
# Runtime: 60 ms, faster than 93.50% of Python3 online submissions for Maximum Subarray.
# Memory Usage: 14.5 MB, less than 5.69% of Python3 online submissions for Maximum Subarray.

I didn't read much because there was an image that dynamic programming was difficult to understand, but when I wrote it, it seems that memory can be made more efficient and faster, so it seems better to study hard.

If there is a good answer, I will add it.

Let Code Day18 starting from zero "53. Maximum Subarray"

Overview

problem

solution