Skip to main content

May-15 2020 Challenge

15. Maximum Sum Circular Subarray

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array.  

(Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once.  

(Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)

Example 1:

Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3

Example 2:

Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

Example 3:
Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4

Example 4:
Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3

Example 5:
Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1

Note:
  1. -30000 <= A[i] <= 30000
  2. 1 <= A.length <= 30000

Solution in C++:


class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int nocircle= help(A), sum= 0;
        if(nocircle < 0)
            return nocircle;
        
        vector<int> tmp= A;
        for(auto &n: tmp){
            sum+= n;
            n*= -1;
        }   
        
        int circle= sum+ help(tmp);
        return max(circle, nocircle);
    }
    int help(vector<int>& A){
        int max_endhere= 0, max_sofar= INT_MIN;
        for(int i= 0; i< A.size(); i++){
            if(max_endhere < 0)
                max_endhere= A[i];
            else
                max_endhere+= A[i];
            
            max_sofar= max(max_sofar, max_endhere);
        }
        return max_sofar;
    }
};

 compensation leetcode challenge leetcode decode ways leetcode dark theme leetcode dfs leetcode data structures leetcode decode ways ii leetcode discuss leetcode daily temperatures leetcode edit distance leetcode explore leetcode easy problems leetcode
Leetcode day 15
errichto leetcode editor leetcode extension leetcode egg drop leetcode editorial leetcode flood fill leetcode find the town judge lgeetcode free leetcode founder leetcode for beginners 
Labels:

Comments

Post a Comment

Popular posts from this blog

Leetcode 371. Sum of Two Integers. C++ / Java

371 .  Sum of Two Integers   Given two integers  a  and  b , return  the sum of the two integers without using the operators   +   and   - .   Example 1: Input: a = 1, b = 2 Output: 3 Example 2: Input: a = 2, b = 3 Output: 5   Constraints: -1000 <= a, b <= 1000 Solution :  C++ : class Solution { public: int getSum(int a, int b) { if (b==0) return a; int sum = a ^ b; int cr = (unsigned int) (a & b) << 1; return getSum(sum, cr); } }; Java :  class Solution { public int getSum(int a, int b) { while(b != 0){ int tmp = (a & b) << 1; a = a ^ b; b = tmp; } return a; } } Explaination :
Post a Comment
Read more

Leetcode 217. Contains Duplicate. Python (Easiest Approach ✅)

217 .  Contains Duplicate   Given an integer array  nums , return  true  if any value appears  at least twice  in the array, and return  false  if every element is distinct.   Example 1: Input: nums = [1,2,3,1] Output: true Example 2: Input: nums = [1,2,3,4] Output: false Example 3: Input: nums = [1,1,1,3,3,4,3,2,4,2] Output: true   Constraints: 1 <= nums.length <= 10 5 -10 9  <= nums[i] <= 10 9 class Solution: def containsDuplicate(self, nums: List[int]) -> bool: hs = set() for n in nums: if n in hs: return True hs.add(n) return False Explaination :
Post a Comment
Read more

Leetcode 322. Coin Change. Python (Greedy? vs DP?)

322 .  Coin Change You are given an integer array  coins  representing coins of different denominations and an integer  amount  representing a total amount of money. Return  the fewest number of coins that you need to make up that amount . If that amount of money cannot be made up by any combination of the coins, return  -1 . You may assume that you have an infinite number of each kind of coin.   Example 1: Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 Example 2: Input: coins = [2], amount = 3 Output: -1 Example 3: Input: coins = [1], amount = 0 Output: 0   Constraints: 1 <= coins.length <= 12 1 <= coins[i] <= 2 31  - 1 0 <= amount <= 10 4   Solution : class Solution:     def coinChange(self, coins: List[int], amount: int) -> int:         dp = [amount + 1] * (amount + 1) #[0...7]         dp[0] = 0        ...
Post a Comment
Read more