Maximum Ascending Subarray Sum

Problem Statement

  • Aapko ek positive integers ka array diya gaya hai, nums. Aapko maximum possible sum return karna hai ek ascending subarray ka nums mein.

    Definitions:

    • Subarray: Array ke continuous sequence of numbers.

    • Ascending Subarray: Ek subarray tab ascending hota hai jab uske saare elements strictly increasing order mein hon. Matlab, har i ke liye jahan l <= i < r ho, nums[i] < nums[i+1].

    Examples:

    1. Input: nums = [10, 20, 30, 5, 10, 50] Output: 65 Explanation: [5, 10, 50] ek ascending subarray hai jiska maximum sum 65 hai.

    2. Input: nums = [10, 20, 30, 40, 50] Output: 150 Explanation: [10, 20, 30, 40, 50] ek ascending subarray hai jiska maximum sum 150 hai.

    3. Input: nums = [12, 17, 15, 13, 10, 11, 12] Output: 33 Explanation: [10, 11, 12] ek ascending subarray hai jiska maximum sum 33 hai.

    Constraints:

    • 1 <= nums.length <= 100

    • 1 <= nums[i] <= 100

Maximum Ascending Subarray Sum

Single-Pass Greedy Approach: Hum ek hi baar array ko traverse karenge.

Running Sum: Hum har ascending sequence ke liye ek running sum track karenge.

Update Maximum Sum: Jaise hi hume ek new ascending sequence milti hai, hum apna running sum update karte hain aur agar wo sum maximum se zyada hai, to maximum sum bhi update karte hain.

Initialize Variables:

currentSum = nums[0] → Yeh variable current ascending subarray ka sum track karega.

maxSum = currentSum → Yeh variable maximum sum ko store karega jo encounter kiya gaya hai.

Array ko Iterate karo (O(n)):

Har element ke liye check karo:

Agar nums[i] > nums[i-1], to nums[i] ko currentSum mein add karo (ascending subarray ko extend karo).

Warna, currentSum ko nums[i] se reset karo (naya subarray start karo).

Har step ke baad, agar currentSum maxSum se bada ho, to maxSum ko update karo.

Return maxSum:

Sabhi elements process karne ke baad maxSum return karo.

Time Complexity:

  1. Traversal: Array ko ek baar traverse kar rahe hain, har element ko sirf ek baar visit karte hain.

  2. Operations: Har element ke liye ek simple comparison aur addition/subtraction kar rahe hain, jo constant time operations hain.

Isiliye, time complexity O(n) hai, jahan n array ke elements ka number hai.

Space Complexity:

  1. Extra Space: Hum do extra variables use kar rahe hain: currentSum aur maxSum.

  2. No Extra Data Structures: Hum koi extra array ya data structure use nahi kar rahe, bas kuch constant space.

Solution

				
					/**
 * @param {number[]} nums
 * @return {number}
 */
var maxAscendingSum = function(nums) {
    // currentSum ko initialize karo, jo current ascending subarray ka sum track karega
    let currentSum = nums[0], maxSum = currentSum; // maxSum ko bhi initialize karo, jo maximum sum ko store karega
    
    // Array ko traverse karte hain
    for (let i = 1; i < nums.length; i++) {
        // Agar current element pichle element se bada hai
        if (nums[i] > nums[i - 1]) {
            currentSum += nums[i]; // Ascending subarray ko extend karo
        } else {
            currentSum = nums[i]; // Naya subarray start karo
        }
        // maxSum ko update karo agar currentSum zyada hai
        maxSum = Math.max(maxSum, currentSum);
    }
    
    // Final maximum sum return karo
    return maxSum;
};

				
			
  • Function Definition:

    • var maxAscendingSum = function(nums) { ... }: Yeh function nums naam ke array ko parameter ke roop mein leta hai aur maximum ascending subarray ka sum return karta hai.

  • Variable Initialization:

    • let currentSum = nums[0], maxSum = currentSum;: Pehle element ko currentSum aur maxSum mein initialize karte hain. currentSum current ascending subarray ka sum track karega aur maxSum maximum sum ko track karega.

  • Array Traversal:

    • for (let i = 1; i < nums.length; i++) { ... }: Array ke doosre element se lekar last element tak loop chalayenge.

  • Check Ascending Condition:

    • if (nums[i] > nums[i - 1]) { ... } else { ... }: Har element ke liye check karenge ki kya woh pichle element se bada hai.

      • if (nums[i] > nums[i - 1]) { currentSum += nums[i]; }: Agar bada hai, to currentSum mein current element ko add karenge (ascending subarray ko extend karenge).

      • else { currentSum = nums[i]; }: Agar bada nahi hai, to currentSum ko current element se reset karenge (naya subarray start karenge).

  • Update Maximum Sum:

    • maxSum = Math.max(maxSum, currentSum);: Har step ke baad check karenge ki currentSum maxSum se bada hai ya nahi. Agar bada hai, to maxSum ko update karenge.

  • Return Result:

    • return maxSum;: Loop complete hone ke baad, maximum ascending subarray ka sum maxSum return karenge.

Solution

				
					class Solution {
public:
    int maxAscendingSum(vector<int>& nums) {
        // currentSum ko initialize karo, jo current ascending subarray ka sum track karega
        int currentSum = nums[0], maxSum = currentSum; // maxSum ko bhi initialize karo, jo maximum sum ko store karega
        
        // Array ko iterate karte hain
        for (int i = 1; i < nums.size(); i++) {
            // Agar current element pichle element se bada hai
            if (nums[i] > nums[i - 1]) {
                currentSum += nums[i]; // Ascending subarray ko extend karo
            } else {
                currentSum = nums[i]; // Naya subarray start karo
            }
            // maxSum ko update karo agar currentSum zyada hai
            maxSum = max(maxSum, currentSum);
        }
        
        // Final maximum sum return karo
        return maxSum;
    }
};

				
			
      • Class Declaration:

        • class Solution { ... };: Yeh class Solution ke naam se define ki gayi hai.

      • Function Declaration:

        • int maxAscendingSum(vector<int>& nums) { ... }: Yeh function maxAscendingSum ka naam hai, jo ek vector nums ko parameter ke roop mein leta hai aur maximum ascending subarray ka sum return karta hai.

      • Variable Initialization:

        • int currentSum = nums[0], maxSum = currentSum;: Pehle element ko currentSum aur maxSum mein initialize karte hain. currentSum current ascending subarray ka sum track karega aur maxSum maximum sum ko track karega.

      • Array Traversal:

        • for (int i = 1; i < nums.size(); i++) { ... }: Array ke doosre element se lekar last element tak loop chalayenge.

      • Check Ascending Condition:

        • if (nums[i] > nums[i - 1]) { ... } else { ... }: Har element ke liye check karenge ki kya woh pichle element se bada hai.

          • if (nums[i] > nums[i - 1]) { currentSum += nums[i]; }: Agar bada hai, to currentSum mein current element ko add karenge (ascending subarray ko extend karenge).

          • else { currentSum = nums[i]; }: Agar bada nahi hai, to currentSum ko current element se reset karenge (naya subarray start karenge).

      • Update Maximum Sum:

        • maxSum = max(maxSum, currentSum);: Har step ke baad check karenge ki currentSum maxSum se bada hai ya nahi. Agar bada hai, to maxSum ko update karenge.

      • Return Result:

        • return maxSum;: Loop complete hone ke baad, maximum ascending subarray ka sum maxSum return karenge.