What is the difference between non decreasing, increasing and strictly increasing sub array in c and c++? how can I count the number of non-decreasing sub array? plz explain with example and code.

asked 10 Oct '15, 07:28

Undefined%20Mehedi's gravatar image

Undefined Mehedi
457

edited 10 Oct '15, 08:15


Answer of Section 1: Increasing, Non-Decreasing, Strictly Increasing

ধরুন একটা Array দেয়া আছে এমন -

1, 2, 3, 3, 4

এখানে দেখুন প্রতিটা ইলিমেন্ট তার ডান পাশের ইলিমেন্ট এর চাইতে ছোট বা ডান পাশের ইলিমেন্ট এর সমান । Array এই সিচুয়েশন কে বলা হয় Non-Decreasing মানে ক্রমহহ্রাসমান নয় ।

Increasing এর ক্ষেত্রে মাঝে মাঝে Increasing এবং Non-decreasing দুটোই একই অর্থ বহন করে । আবার মাঝে মাঝে Increasing এবং Strictly Increasing দুটোই একই অর্থ বহন করে ।

প্রব্লেমের ধরন অনুসারে আপনাকে ঠিক করে নিতে হবে আসলে কি বুঝাতে চেয়েছেন প্রব্লেম সেটার । Strictly Increasing মানে হল আবশ্যিক ভাবে ক্রম বর্ধমান । ধরুন একটা উদাহরন -

1, 2, 3, 4, 5

এখানে প্রতিটা ইলিমেন্ট তার ডান পাশের ইলিমেন্ট এর চাইতে বড় । এই সিচুয়েশন কে আপনি Strictly Increasing বলতে পারবেন ।

Answer of Section 2 : Number of Non-decreasing sub-array.

ধরে নিচ্ছি আপনি যে প্রশ্ন টি দিয়েছেন সেটাতে Contiguous Element এর জন্য Sub Array বের করতে বলেছেন ( আপনি প্রশ্নে পরিষ্কার করেন নি তাই আমি আমার Assumption এর ভিত্তিতে উত্তর দিচ্ছি ) । সেক্ষেত্রে আপনি লুপ চালিয়ে দেখতে পারেন পাশাপাশি কয়টা ইলিমেন্ট Non-decreasing অর্ডারে আছে । সেগুলো গণনা করে নিবেন । ধরেন এমন আছে X টা । তাহলে Answer হবে 2x টা । এভাবে যতক্ষন না পর্যন্ত একটা ছোট ইলিমেন্ট পাচ্ছেন ততক্ষন গণনা করতে থাকুন । যখনি ছোট ইলিমেন্ট পাবেন তখন Answer এর সাথে 2x যোগ করে দিবেন এবং X এর মান 0 করে দিবেন ।

Pseudo Code

X = 0
Iterate over the array
   if(Array[i]<=Arrar[i+1])
       X++;
   else
      X++;
      Answer = Answer + 2^X;
      X = 0;
X++;
Answer = Answer + 2^X ; // এই লাইন কেন দিয়েছি বুঝার জন্য উদাহরন 1, 2, 3 চিন্তা করুন ।  
return Answer;

Hope it helps. Thank You.

permanent link

answered 25 Apr, 04:31

ssavi's gravatar image

ssavi
842

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×386
×118
×54

question asked: 10 Oct '15, 07:28

question was seen: 709 times

last updated: 25 Apr, 04:31