Comments (10)
i would like to work on this project
from algorithmic-pseudocode.
Sure, go ahead. Make sure to share your approach first.
from algorithmic-pseudocode.
My first approach using Dynamic Programming and more specifically divide and conquer techique
It is java code and passes LeetCode test.
public class Solution {//using divide and conquer technique,dividing the problem by the last balloon to burst
public int maxCoins(int[] nums)
{
// Initialize the ArrayB stands for Array of Balloons and extend the list with top=bottom=1
int Arrayb[] = new int[nums.length + 2];
Arrayb[0] = 1;
Arrayb[Arrayb.length-1] = 1;
for (int i = 0; i < nums.length; i++)
{
Arrayb[i+1] = nums[i];
}
// MCstep stands for max coins at every step
int MCstep[][] = new int[Arrayb.length][Arrayb.length];
for (int i =0; i < Arrayb.length; i++) //Intialiazing MCstep to zero
{
for (int j = 0; j < Arrayb.length; j++)
{
MCstep[i][j] = 0;
}
}
for (int k=2; k< Arrayb.length;++k) //from this 3 loops we assume that complexity is o(n^3)
{
for (int left=0; left<Arrayb.length-k;++left)
{
int right = left + k;
for (int i = left + 1; i < right; ++i)// the balloon i is the last balloon to burst
{
MCstep[left][right] = Math.max(MCstep[left][right],
Arrayb[left] * Arrayb[i] * Arrayb[right] + MCstep[left][i] + MCstep[i][right]);
}
}
}
return MCstep[0][Arrayb.length-1];
}
}
from algorithmic-pseudocode.
Looks good. You can start working on the pseudocode now.
from algorithmic-pseudocode.
This is my attempt for the pseudocode
% Set the Page Layout
\documentclass[12pt]{article}
\usepackage[inner = 2.0cm, outer = 2.0cm, top = 2.0cm, bottom = 2.0cm]{geometry}
% Package to write pseudo-codes
\usepackage{algorithm}
% Remove the 'end' at the end of the algorithm
\usepackage[noend]{algpseudocode}
% Define Left Justified Comments
\algnewcommand{\LeftComment}[1]{\Statex \(\triangleright\) #1}
% Remove the Numbering of the Algorithm
\usepackage{caption}
\DeclareCaptionLabelFormat{algnonumber}{Algorithm}
\captionsetup[algorithm]{labelformat = algnonumber}
\newcommand{\To}{\textbf{ to }}
\begin{document}
\begin{algorithm}
\caption{Find the maximum coins you can collect by bursting the balloons wisely.}
\begin{algorithmic}[1]
\Require An array of Balloons as input
\Statex
\Function{$Max\_Coins$}{$BArray$}
\Statex
\State $BalloonArraylength \gets BArraylength+2$
\State $BalloonArray[0] \gets 1$
\Comment{Initialise the top and bottom of the BalloonArray to 1}
\State $BalloonArray[BalloonArraylength-1] \gets 1$
\For{$i=1 \To BalloonArraylength-2$}
\Comment{Initialise the rest of BalloonArray by indexing it to Barray}
\State $BalloonArray[i] \gets Barr[i]$
\EndFor
\State $MCarray[i][j] \gets 0 \hfill \forall i \hfill \forall j$
\Comment{Initialise the MaxCoin array}
\Statex
\Comment{Divide and Conquer technique , defining subproblems by the last balloon to burst}
\For{$k = 3\To ArrayBalloonlength$}
\Comment{Complexity O($n^3$)}
\For{$left =1 \To ArrayBalloonlength-k$}
\State $right \gets left+k$
\For{$i=left+2\To right$}
\Comment{i Balloon is the last balloon we burst}
\State $MCarray[left][right] \gets MAX(MCarray[left][right], BalloonArray[left] * BalloonArray[i] * BalloonArray[right] + MCarray[left][i] + MCarray[i][right])$
\EndFor
\EndFor
\EndFor
\State \Return{$ MCarray[0][ArrayBalloonlength-1]$}
\EndFunction
\end{algorithmic}
\end{algorithm}
\end{document}
from algorithmic-pseudocode.
I'm out of town at the moment (without my laptop). I won't be back before 10th. Can you please wait for the review till then? Thanks!
A general tip, avoid using cameCase and use underscores instead. Moreover, any comment should not span more than one line. Keep the comments short (and include an explanation at the end if need be). Right now, the code looks clustered, you can provide blank lines using /Statex.
I'll let you know the other ones on 10th. Till then you can look around for other issues (or create one)
from algorithmic-pseudocode.
i edited the pseudocode and i think is more clear know. I'll wait for your review next week
% Set the Page Layout
\documentclass[12pt]{article}
\usepackage[inner = 1.0cm, outer = 1.0cm, top = 2.0cm, bottom = 2.0cm]{geometry}
% Package to write pseudo-codes
\usepackage{algorithm}
% Remove the 'end' at the end of the algorithm
\usepackage[noend]{algpseudocode}
% Define Left Justified Comments
\algnewcommand{\LeftComment}[1]{\Statex \(\triangleright\) #1}
% Remove the Numbering of the Algorithm
\usepackage{caption}
\DeclareCaptionLabelFormat{algnonumber}{Algorithm}
\captionsetup[algorithm]{labelformat = algnonumber}
\newcommand{\To}{\textbf{ to }}
\begin{document}
\begin{algorithm}
\caption{Find the maximum coins you can collect by bursting the balloons wisely.}
\begin{algorithmic}[1]
\Require An array of Balloons as input
\Statex
\Function{$Max\_Coins$}{$BArray$}
\Statex
\State $BalloonArraylength \gets BArraylength+2$
\State $BalloonArray[0] \gets 1$
\Comment{Initialise the top and bottom of the BalloonArray to 1}
\State $BalloonArray[BalloonArraylength-1] \gets 1$
\Statex
\For{$i=1 \To BalloonArraylength-2$}
\Comment{Indexing BalloonArray to Barray}
\State $BalloonArray[i] \gets Barr[i]$
\EndFor
\Statex
\State $MCarray[i][j] \gets 0$ $\forall i $ $ \forall j$
\Comment{Initialise the MaxCoin array}
\For{$k = 3\To ArrayBalloonlength$}
\Comment{Complexity O($n^3$)}
\Statex
\For{$left =1 \To ArrayBalloonlength-k$}
\State $right \gets left+k$
\Statex
\For{$i=left+2\To right$}
\Comment{i Balloon is the last balloon we burst}
\Statex
\State $MCarray[left][right] \gets MAX(MCarray[left][right],BalloonArray[left]*BalloonArray[i] * BalloonArray[right] + MCarray[left][i] + MCarray[i][right]$
\EndFor
\EndFor
\EndFor
\Statex
\State \Return{$ MCarray[0][ArrayBalloonlength-1]$}
\EndFunction
\end{algorithmic}
\end{algorithm}
Divide and Conquer technique , defining subproblems by the last balloon to burst
\end{document}
from algorithmic-pseudocode.
Thanks. I'll look into it.
Here is a quick tip regarding code sharing in markdown. This retains the formatting and color coding. (The language is tex
)
from algorithmic-pseudocode.
I think that the iterative DP solution doesn't capture the essence of the problem (as the real details are hidden by the implementation specifics).
Based on your iterative solution, I've written a recursive one which is quite expressive. I would appreciate it if you could write the pseudocode for the recursive one (We can include the iterative one at a later stage). If you are busy, I can take this up, No issues.
Here is my solution.
Let me know if you have any issues.
Tips
- It's okay to use the name of the array as
arr
instead ofBArray
. - Mention explicitly that you are adding 2 extra elements in the initial array (Maybe using
push_back/push_front
- Try to accommodate a single statement in a single line. If it gets big, break it into parts
- Define the DP definitions clearly. (
dp[low][high] denotes the profit that can be collected by bursting **all** the balloons in the range (low,high) (Excluding both
lowand
high`). - Avoid
camelCase
and useunder_scores
from algorithmic-pseudocode.
After you're done, make a pull request so that I can review the code line by line (instead of posting in this thread)
from algorithmic-pseudocode.
Related Issues (20)
- Addition of Heapsort and RadixSort HOT 1
- Addition of Bubble sort algorithm pseudo code HOT 2
- Typo in the hacktoberfest label HOT 1
- Addition of iterative version of Binary Search HOT 2
- Addition of Symmetric Tree algorithm pseudocode
- Addition of Symmetric Tree algorithm pseudocode HOT 2
- Addition of Predefined Process - Flowchart Symbols and Their Meanings HOT 2
- Addition of Predefined Process - Examples of Algorithm HOT 2
- Implement a PDF explanation for Bubble Sort Pseudocode HOT 9
- Implement a PDF explanation for Heap Sort Pseudocode HOT 8
- Add an explanation of Task Scheduler to LeetCode Non-Contest Solutions HOT 2
- Addition Decision tree pseudocode HOT 2
- Compare algorithms HOT 4
- Te comparto mi código
- Pseudocode for Union Find Data Structure
- Small Typo :) HOT 2
- Pseudocode for Bipartite Graph Check HOT 1
- Pseudo code for Fibonacci using a dynamic approach HOT 1
- Addition of Quick Sort algorithm
- Pseudocode for Shortest Subarray sorting which sorts the entire array HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from algorithmic-pseudocode.