I got an online test problem where they gave a string of characters and a value for each character. Value of each character is in range [-10, 10]. The problem was to find a substring that starts and ends with same character and has maximum value. The problem easily reduces to a extended version of maximum subarray sum problem after replacing the characters with values. The constraint is the starting and ending values will be same. I came up with a naive solution and was not good enough. Can anyone tell me how to work this out with Kadane's algorithm or any other with a better time complexity?
Maximum subarray sum with same starting and end element
346 Views Asked by Kushal Mondal At
1
There are 1 best solutions below
Related Questions in ARRAYS
- How could you print a specific String from an array with the values of an array from a double array on the same line, using iteration to print all?
- What does: "char *argv[]" mean?
- How to populate two dimensional array
- User input sanitization program, which takes a specific amount of arguments and passes the execution to a bash script
- Function is returning undefined but should be returning a matched object from array in JavaScript
- The rules of Conway's Game of Life aren't working in my Javascript version. What am I doing wrong?
- Array related question, cant find the pattern
- Setting the counter (j) for (inner for loop)
- I want to flip an image (with three channels RGB) horizontally just using array slicing. How can I do it with python?
- Numpy array methods are faster than numpy functions?
- How to enter data in mongodb array at specific position such that if there is only 2 data in array and I want to insert at 5, then rest data is null
- How to return array to ArrayPool when it was rented by inner function?
- best way to remove a word from an array in a react app
- Vue display output of two dimensional array
- Undot Array with Wildcards in Laravel
Related Questions in ALGORITHM
- MCNP 6 - Doubts about cells
- Given partially sorted array of type x<y => first apperance of x comes before first of y, sort in average O(n)
- What is the algorithm behind math.gcd and why it is faster Euclidean algorithm?
- Purpose of last 2 while loops in the merge algorithm of merge sort sorting technique
- Dots and Boxes with apha-beta pruning
- What is the average and worst-case time complexity of my string searching algorithm?
- Building a School Schedule Generator
- TC problem 5-2:how to calculate the probability of the indicator random variable?
- LCA of a binary tree implemented in Python
- Identify the checksum algorithm
- Algorithm for finding a subset of nodes in a weighted connected graph such that the distance between any pair nodes are under a postive number?
- Creating an efficent and time-saving algorithm to find difference between greater than and lesser than combination
- Algorithm to find neighbours of point by distance with no repeats
- Asking code suggestions about data structure and algorithm
- Heap sort with multithreading
Related Questions in KADANES-ALGORITHM
- Finding the Maximum Inversion Sum of an Array
- Find array of maximum subarray sum using kadane's Algorithm
- Maximum Sum of Two Non-Overlapping Subarrays of any length
- Does a one pass solution exist in a problem of sorting an array containing only 0s, 1s, 2s, and 3s?
- Implementation of Kadane's Algorithm is not working for one particular array
- Understanding what's happening in the Kadane Algorithm (Python)
- Why this code is returning wrong value? inputs= 5 ,{ -1,4,-6,7,-4}
- Maximum subarray problem - min value solution?
- Array operations for maximum sum
- Version of Kadane's Algorithm with result max sub-matrix of fixed dimensions
- Debugging: Largest Sum Contiguous Subarray
- What are overlapping subproblems in Dynamic Programming (DP)?
- Maximum subarray sum with same starting and end element
- Javascript function that finds largest subarray
- Javascript Algorithm Maximum subarray
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular # Hahtags
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
This question is designed to make Kadane's algorithm a bad fit.
You can still do it quickly and easily, though:
Iterate through the sequence, keeping track of the cumulative sum of values preceding each letter.
For each letter, remember the smallest preceding sum seen so far
At each letter, the maximum value sequence that ends there starts at the instance of the same letter with the smallest preceding sum seen so far. Note that that might be same position for a sequence with length 1.
It's easy to calculate the value of that best sequence ending at each letter: letter_value + preceding_sum - smallest_preceding_sum_for_same_letter. Remember the most valuable sequence you find.