Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continues to punch the card for the 17th day 🎈!
🚀 Algorithm 🚀

🌲 Example of original problem

Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.

The sample1: Input: nums = [2 -.1.- 3.4.- 1.2.1.- 5.4] output:6Continuous subarrays [4.- 1.2.1] and maximum, for6 。
Copy the code
The sample2: Input: nums = [1] output:1
Copy the code
The sample3: Input: nums = [0] output:0
Copy the code
The sample4: Input: nums = [- 1] output:- 1
Copy the code
The sample5: Input: nums = [- 100000.] output:- 100000.
Copy the code

Tip:

  • 1 <= nums.length <= 3 * 104
  • -105 <= nums[i] <= 105

🌻C# method 1: dynamic programming

The core idea of dynamic programming is to call subproblems repeatedly

  • Sum represents the sum of the current continuous subarray, Max represents the current and largest continuous subarray.
  • Sum = nums[I]; sum = nums[I]; sum = nums[I]; Otherwise sum plus nums[I];
  • The sum obtained each time is compared with Max to get the current maximum sum.

Code:

public class Solution {
    public int MaxSubArray(int[] nums) {
        int sum = nums[0];
        int max = nums[0];
        for(int i = 1; i < nums.Length; i++)
        {
            if(nums[i] > sum + nums[i]) sum = nums[i];
            else sum = sum + nums[i];
            if(sum > max) max = sum;
        }
        returnmax; }}Copy the code

The execution result

By execution time:88Ms, in all C# beat 87.62% of users in submissionMemory consumption:25.5MB, in all CBeat 25.74% of users in # submission
Copy the code

Complexity analysis

Time: O(n) Space: O(1)
Copy the code

🌻C# method two: divide-and-conquer

Thinking analyticalThis divide and conquer method, I also did not see very clear, here buckle solution put up for everyone’s reference!

Code:

public class Solution {
    public class Status {
        public int lSum, rSum, mSum, iSum;
        public Status(int lSum_, int rSum_, int mSum_, int iSum_){ lSum = lSum_; rSum = rSum_; mSum = mSum_; iSum = iSum_; }}public Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = Math.Max(l.lSum, l.iSum + r.lSum);
        int rSum = Math.Max(r.rSum, r.iSum + l.rSum);
        int mSum = Math.Max(Math.Max(l.mSum, r.mSum), l.rSum + r.lSum);
        return new Status(lSum, rSum, mSum, iSum);
    }

    public Status getInfo(int[] a, int l, int r) {
        if (l == r) {
            return new Status(a[l], a[l], a[l], a[l]);
        }
        int m = (l + r) >> 1;
        Status lSub = getInfo(a, l, m);
        Status rSub = getInfo(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    public int MaxSubArray(int[] nums) {
        return getInfo(nums, 0, nums.Length - 1).mSum; }}Copy the code

The execution result

By execution time:76Ms, in all CBeat 99.63% of users in # submissionsMemory consumption:26.9MB, in all CBeat 5.03% of users in # submissions
Copy the code

Complexity analysis

Time: O(n) Space: O(long n)
Copy the code

🌻Java Method 1: Dynamic planning

Thinking analytical

Code:

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        returnmaxAns; }}Copy the code

The execution result

By execution time:1Ms, beat out all Java commits92.33% user memory consumption:38.2MB, beat out all Java commits79.37% of the userCopy the code

Complexity analysis

Time: O(n) Space: O(1)
Copy the code

🌻Java Method 2: Divide and conquer

C# and above the second solution of a train of thought, code is different

Code:

class Solution {
    public class Status {
        public int lSum, rSum, mSum, iSum;

        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum; }}public int maxSubArray(int[] nums) {
        return getInfo(nums, 0, nums.length - 1).mSum;
    }

    public Status getInfo(int[] a, int l, int r) {
        if (l == r) {
            return new Status(a[l], a[l], a[l], a[l]);
        }
        int m = (l + r) >> 1;
        Status lSub = getInfo(a, l, m);
        Status rSub = getInfo(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    public Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = Math.max(l.lSum, l.iSum + r.lSum);
        int rSum = Math.max(r.rSum, r.iSum + l.rSum);
        int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
        return newStatus(lSum, rSum, mSum, iSum); }}Copy the code

The execution result

By execution time:76Ms, in all CBeat 99.63% of users in # submissionsMemory consumption:26.9MB, in all CBeat 5.03% of users in # submissions
Copy the code

Complexity analysis

Time: O(n) Space: O(long n)
Copy the code

💬 summary

  • Today is the seventeenth day of buckle algorithm clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!