Time complexity about Maximum subarray

I recently came across a function called the strawman algorithm which the pseudo code looks like this:

StrawmanSubarray(A):   Initialize bestsum = A[0]        For left=0 to n-1:         For right = left to n-1:            Compute sum A[left] + . . . + A[right]            If sum > bestsum: bestsum = sum 

The time complexity is Θ (n^3), and I don’t quite get where is the 3rd n comes from to get Θ (n^3)?

Algorithm- Find the length of largest subarray having sum greater than k

I tried to solve this problem but could not do it better than O(n^2).

My Algorithm: 1.calculate prefixsum 2.for i 1...n   for j 1...i  if(presum[i]-presum[j-1]>k)   ans=max(ans,i-j); 

However, this is inefficient for large values of n.Can someone help me with optimized algorithm along with code preferably in c++.

Smallest subarray problem

Say you have an array of integers like [1, 2, 3, 4, 5, 6], the problem is to find the smallest way to break up the array into sub-arrays where each sub-array satisfies the following requirement:

  • sub-array.first_integer and sub-array.last_integer must have a common divisor that is not 1.

So for [1, 2, 3, 4, 5, 6] the answer would be 2, because you can break it up like [1] and [2, 3, 4, 5, 6], where 2 and 6 have a common divisor of 2 (which is > 1 so it meets the requirement).

You can assume the array can be huge but the numbers are not too big. Is there a way to do this in n or n*log(n) time? I think with dp and caching n^2 is possible but not sure how to do it faster.

Contiguous Subarray Max

I’m trying to solve the contiguous subarray problem on CodeSignal & I came up with the following solution which is based off of Kadane’s Algorithm. My implementation passed the given test data set however upon submission, it failed. There’s no reason given on CodeSignal & I can’t look at it since I just started doing it & have less coins.

I can’t figure out why my solution is failing but the solution based on online pseudo code works, even though my solution passed the preliminary tests. I think it might have to do with integer overflow or some other reason that’s why I’ve come here to seek help from experts.

My implementation:

 public int findConsecutiveSubarray(int nums[]) {     int currentSum = 0;     int max =Integer.MIN_VALUE;;      int i=0;     while(i < nums.length) {         currentSum += nums[i];          if(max < currentSum)             max = currentSum;          if(max < nums[i]) {             max = nums[i];             currentSum = nums[i];         }          i++;     }     System.out.println("maxSum : "+ max);     return max; } 

Solution based on online:

int arrayMaxConsecutiveSum2(int[] nums) {         int currentMax = 0;         int globalMax = 0;                  globalMax = currentMax = nums[0];                  for(int i=1; i<nums.length; i++) {             currentMax = Math.max(nums[i], currentMax + nums[i]);             globalMax = Math.max(globalMax, currentMax);         }          return globalMax; } 

What is exactly an empty Sub-array

I read the question in Exercise 4.1-4 in Introduction To Algorithms:

Suppose we change the definition of the maximum-subarray problem to allow the result to be an empty subarray, where the sum of the values of an empty subarray is 0. How would you change any of the algorithms that do not allow empty subarrays to permit an empty subarray to be the result?

I cannot get what’s an empty sub-array.

I came across the point that a single number can be returned if the array consists of negative elements only.

Please can anyone explain the concept of an empty sub-array? And how can we have an empty sub-array?

Even if a single element is returned it still means that sub-array is not empty. Please clear the doubt.

Thank you.

Cannot understand the relevance of $\binom{n-1}{2}$ subarrays in The Maximum Sub-array Problem

I recently came across the sentence in the Book Introduction to Algorithms section 4.1 The maximum sub-array problem:

We still need to check $ \binom{n-1}{2} = \Theta(n^2)$ subarrays for a period of $ n$ days.

Here $ n$ is the number of days taken as an example to show the changes in price of stock.

We can consider this is the size of an array A.

Where we are provided with an Array A and we need to find the net change is maximum from the first day to the last day.

To explain more specifically it means for an array $ A$ of size $ n$ we need to check $ \binom{n-1}{2}$ subarrays.

But, I cannot understand how we need $ \binom{n-1}{2}$ sub-arrays?

If we take an array of size 5 could someone please explain to me why we need only 6 sub-arrays. Won’t the sub-arrays be:

[1...5] [1...4] [1...3] [1...2]  [2...4] [2...5]   [3...5] [4...5] 

Please correct me if I am wrong. References: Maximum Subarray Problem

The Maximum Sub-array problem Thank you.

Subarray with given sum

What are they asking and how can I solve it? https://practice.geeksforgeeks.org/problems/subarray-with-given-sum/0

Given an unsorted array A of size N of non-negative integers, find a continuous sub-array which adds to a given number S.

Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. The first line of each test case is N and S, where N is the size of array and S is the sum. The second line of each test case contains N space separated integers denoting the array elements.

Output: For each testcase, in a new line, print the starting and ending positions(1 indexing) of first such occuring subarray from the left if sum equals to subarray, else print -1.

Constraints:

1 <= T <= 100

1 <= N <= 107

1 <= Ai <= 1010

Example:

Input:

2

5 12

1 2 3 7 5

10 15

1 2 3 4 5 6 7 8 9 10

Output:

2 4

1 5

Explanation:

Testcase1: sum of elements from 2nd position to 4th position is 12

Testcase2: sum of elements from 1st position to 5th position is 15

Problem states: “The first line of input contains an integer T”. Where? I see the one parameter as a String array. Why?

import java.util.*; import java.lang.*; import java.io.*;  class GFG {     public static void main (String[] args) {         //code     } } 

There is a public static void main method. Void methods cannot return values, so it’s not going to return a value. How do you understand the question?

Longest subarray with sum at most K

The question is:

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

For example: A=[5,2,-1,0,3],K=1, the result is [2,-1,0]

I am inspired by Shortest Subarray with Sum at Least K. Is it possible to solve this corresponding problem with a monotonic queue? If True, how? If not, Why?

I have struggled with it for a long time. Hope for your help.

Maximum Sum SubArray – Naive Implementation

I am looking at a problem that is often asked in interview settings. The problem statement is:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

I want to talk about the naive solution, where we generate all contigous subarrays, take their sums, and find the maximum sum. Here is an implementation of the naive solution:

function maxSubArray(arr) {   let max = null;    for (let i = 0; i < arr.length; i++) {     const startIdx = i;      for (let j = i; j < arr.length; j++) {       let sum = 0;        for (let k = i; k <= j; k++) {         sum = sum + arr[k];       }        if (max === null || max < sum) {         max = sum;       }     }   }    return max; }  

I know that this solution runs in O(n^3), but I do not understand why that is the case. If we “generate” all possible contigous subarrays, I can explain why that is an O(n^2) operation:

Let’s say that our input array is 4. We can create 1 contigous subarray of length 4; 3 contigous subarrays of length 3; 3 contigous subarrays of length 2, and 4 contigous subarrays of length 1. In other words, the number of contigous subarrays for an array of length n is the sum of 1 to n, or (n * (n + 1)) / 2. In asymptotic analysis, that is O(n^2).

Now, I understand that summing up each individual subarray is **not* free, but here is where I am stuck. I do not know how to “add the work that we do to get the sum of each subarray” to my existing time complexity of O(n^2).